Vertex deletion problems on chordal graphs
From MaRDI portal
Publication:1786595
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
split graphchordal graphhereditary propertyvertex deletion problem(unit) interval graphmaximum (induced) subgraph
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