Graph modification problem for some classes of graphs

DOI10.1016/J.JDA.2016.06.003MaRDI QIDQ350726zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

chordalchordal bipartitegraph completiongraph deletionstrongly chordal

Mathematics Subject Classification ID

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)

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

Cites work

• Characterizations of strongly chordal graphs
• Chordal bipartite completion of colored graphs
• Classes of bipartite graphs related to chordal graphs
• Complexity classification of some edge modification problems
• Computing the Minimum Fill-In is NP-Complete
• Graph Classes: A Survey
• NP-completeness results for edge modification problems
• Node-Deletion Problems on Bipartite Graphs
• 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
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Strongly chordal and chordal bipartite graphs are sandwich monotone

Cited in

(5)

• Exact-2-relation graphs
• scientific article; zbMATH DE number 1420899 (Why is no real title available?)
• Modifying a graph using vertex elimination
• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
• NP-completeness results for edge modification problems

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)