Graph modification problem for some classes of graphs

DOI10.1016/j.jda.2016.06.003zbMath1355.68107OpenAlexW2443920594MaRDI QIDQ350726

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Exact-2-relation graphs ⋮ Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations

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

This page was built for publication: Graph modification problem for some classes of graphs