Graph Modification Problem for Some Classes of Graphs

Author(s)

R. Sritharan, University of DaytonFollow

Document Type

Article

Publication Date

5-2016

Publication Source

Journal of Discrete Algorithms

Abstract

The issue of determining the complexity of modification problems for chordal bipartite graphs has been raised multiple times in the literature. We show that the completion and deletion problems for chordal bipartite graphs are NP-hard. The corresponding problems for weakly chordal graphs are already known to be hard. As a byproduct, we obtain results on modification problems for a variety of related classes of graphs and also simplify the arguments for the class of weakly chordal graphs.

Inclusive pages

32-37

ISBN/ISSN

1570-8667

Comments

Permission documentation on file.

Copyright

Copyright © 2016, Elsevier

Publisher

Elsevier

Volume

38-41

Peer Reviewed

yes

eCommons Citation

Sritharan, R., "Graph Modification Problem for Some Classes of Graphs" (2016). Computer Science Faculty Publications. 172.
https://ecommons.udayton.edu/cps_fac_pub/172