Graph modification problem for some classes of graphs
DOI10.1016/J.JDA.2016.06.003zbMATH Open1355.68107OpenAlexW2443920594MaRDI QIDQ350726FDOQ350726
Authors: R. Sritharan 
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
Recommendations
- NP-completeness results for edge modification problems
- Publication:4944968
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Vertex deletion problems on chordal graphs
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)
Cites Work
- Graph Classes: A Survey
- Characterizations of strongly chordal graphs
- Node-Deletion Problems on Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- Complexity classification of some edge modification problems
- NP-completeness results for edge modification problems
- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Classes of bipartite graphs related to chordal graphs
- Chordal bipartite completion of colored graphs
- Single-Edge Monotonic Sequences of Graphs and Linear-Time Algorithms for Minimal Completions and Deletions
- Strongly chordal and chordal bipartite graphs are sandwich monotone
- On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
Cited In (5)
This page was built for publication: Graph modification problem for some classes of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q350726)
