On the \(d\)-claw vertex deletion problem
From MaRDI portal
Publication:6182678
DOI10.1007/s00453-023-01144-wOpenAlexW4383552485MaRDI QIDQ6182678
Van Bang Le, Sheng-Lung Peng, Sun-Yuan Hsieh, Hoàng-Oanh Le
Publication date: 25 January 2024
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-023-01144-w
Cites Work
- Unnamed Item
- A fast branching algorithm for cluster vertex deletion
- Improved upper bounds for vertex cover
- The node-deletion problem for hereditary properties is NP-complete
- Computing independent sets in graphs with large girth
- Geometric algorithms and combinatorial optimization
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- Vertex deletion problems on chordal graphs
- Linear-time algorithms for eliminating claws in graphs
- Faster parameterized algorithm for cluster vertex deletion
- Improved approximation algorithms for hitting 3-vertex paths
- Parameterized algorithm for 3-path vertex cover
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the \(d\)-claw vertex deletion problem
- Minimum Edge Dominating Sets
- Minimum-weight triangulation is NP-hard
- Node-Deletion Problems on Bipartite Graphs
- The approximation of maximum subgraph problems
- Vertex Deletion Problems on Chordal Graphs
- Inapproximability of $H$-Transversal/Packing
- Hard tiling problems with simple tiles
- Analyzing the 3-path vertex cover problem in planar bipartite graphs
- A survey of parameterized algorithms and the complexity of edge modification
