Approximation algorithm for the minimum connected k-path vertex cover problem

DOI10.1007/978-3-319-12691-3_56MaRDI QIDQ2942448zbMATH OpenOpenAlexFDO

Authors X. Li, Zhao Zhang, Xiaohui 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)

Recommendations

• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• Approximation algorithms for minimum weight connected 3-path vertex cover
• On approximability of connected path vertex cover

Cites work

• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• Graph theory
• Minimum \(k\)-path vertex cover
• On computing the minimum 3-path vertex cover and dissociation number of graphs
• On the hardness of approximating minimum 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

Cited in

(13)

• Approximating the minimum hub cover problem on planar graphs
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• An approximation algorithm for minimum-cost vertex-connectivity problems
• scientific article; zbMATH DE number 5631194 (Why is no real title available?)
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• On approximability of connected path vertex cover
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• The connected vertex cover problem in \(k\)-regular graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• Approximation algorithm for the minimum weight connected k-subgraph cover problem
• Improved approximation algorithm for minimum weight \(k\)-subgraph cover problem
• A simple LP-free approximation algorithm for the minimum weight vertex cover problem

This page was built for publication: Approximation algorithm for the minimum connected \(k\)-path vertex cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942448)