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

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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
• Node-Deletion Problems on Bipartite Graphs
• NP-completeness results for edge modification problems
• 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

(6)

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

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)