Graph modification problem for some classes of graphs
From MaRDI portal
Publication:350726
DOI10.1016/j.jda.2016.06.003zbMath1355.68107MaRDI QIDQ350726
Publication date: 9 December 2016
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2016.06.003
05C75: Structural characterization of families of graphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Strongly chordal and chordal bipartite graphs are sandwich monotone
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Characterizations of strongly chordal graphs
- Classes of bipartite graphs related to chordal graphs
- Chordal bipartite completion of colored graphs
- NP-completeness results for edge modification problems
- Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
- Node-Deletion Problems on Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- Graph Classes: A Survey
- Complexity classification of some edge modification problems