On the \(d\)-claw vertex deletion problem

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

zbMATH Keywords

graph algorithmvertex covercluster vertex deletionNP-complete problemclaw vertex deletion

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

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