Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover

DOI10.1016/j.dam.2015.12.004zbMath1333.05168OpenAlexW2216743162MaRDI QIDQ266943

Xiaosong Li, Zhao Zhang, Xiao-hui Huang

Publication date: 7 April 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.12.004

zbMATH Keywords

approximation algorithmgirthweightconnected \(k\)-path vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Paths and cycles (05C38) Approximation algorithms (68W25) Connectivity (05C40)

Related Items

The k‐path vertex cover: General bounds and chordal graphs ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ PTAS for minimum \(k\)-path vertex cover in ball graph ⋮ Approximation algorithm for minimum connected 3-path vertex cover ⋮ Approximation algorithms for minimum weight connected 3-path vertex cover ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ 3-path vertex cover and dissociation number of hexagonal graphs

Cites Work

• Unnamed Item
• On the weighted \(k\)-path vertex cover problem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• On the hardness of approximating minimum vertex cover
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• On the \(k\)-path vertex cover of some graph products
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Minimum \(k\)-path vertex cover
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• The vertex cover \(P_3\) problem in cubic graphs
• On the vertex \(k\)-path cover
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• Node-Deletion NP-Complete Problems

This page was built for publication: Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover