Vertex deletion problems on chordal graphs

DOI10.1016/j.tcs.2018.05.039zbMath1401.68114arXiv1707.08690OpenAlexW2964176371MaRDI QIDQ1786595

Yota Otachi, Jie You, Yixin Cao, Yuping Ke

Publication date: 24 September 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.08690

zbMATH Keywords

split graphchordal graphhereditary propertyvertex deletion problem(unit) interval graphmaximum (induced) subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Algorithms for deletion problems on split graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ On the \(d\)-claw vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Largest chordal and interval subgraphs faster than \(2^n\)
• Approximate association via dissociation
• Unit interval editing is fixed-parameter tractable
• On rigid circuit graphs
• Dominating sets for split and bipartite graphs
• On split-coloring problems
• The maximum k-colorable subgraph problem for chordal graphs
• The node-deletion problem for hereditary properties is NP-complete
• Some simplified NP-complete graph problems
• Trivially perfect graphs
• On the pathwidth of chordal graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• HAMILTONian circuits in chordal bipartite graphs
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Large Induced Subgraphs via Triangulations and CMSO
• Chordal Editing is Fixed-Parameter Tractable
• Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
• Measuring Indifference: Unit Interval Vertex Deletion
• Node-Deletion Problems on Bipartite Graphs
• Computing the Minimum Fill-In is NP-Complete
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Linear Recognition of Almost Interval Graphs
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Approximation and Kernelization for Chordal Vertex Deletion
• Exact Algorithms via Monotone Local Search
• On the hardness of approximating minimization problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Vertex deletion problems on chordal graphs