Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem

DOI10.1007/978-3-319-12691-3_56zbMath1433.05300OpenAlexW1175062981MaRDI QIDQ2942448

Zhao Zhang, Xiaosong Li, Xiao-hui Huang

Publication date: 11 September 2015

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-12691-3_56

zbMATH Keywords

approximation algorithm\(k\)-path vertex coverconnected \(k\)-subgraph cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• 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
• 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
• Approximation algorithm for the minimum weight connected \(k\)-subgraph cover problem
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs