Approximation algorithm for the minimum weight connected k-subgraph cover problem

DOI10.1016/J.TCS.2014.03.026MaRDI QIDQ2447765zbMATH OpenOpenAlexFDO

Authors Yaping Zhang, Yishuo Shi, Zhao Zhang

Publication date 29 April 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.03.026

zbMATH Keywords

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Improved approximation algorithm for minimum weight \(k\)-subgraph cover problem
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Approximation algorithms for minimum (weight) connected k-path vertex cover
• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Approximation algorithms for minimum weight connected 3-path vertex cover

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• A unified approach to approximating resource allocation and scheduling
• A unified approximation algorithm for node-deletion problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Design and analysis of approximation algorithms
• Local ratio with negative weights.
• 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

(15)

• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Kernels for packing and covering problems
• Improved approximation algorithm for minimum weight \(k\)-subgraph cover problem
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• Approximation algorithms for minimum weight partial connected set cover problem
• Approximation algorithm for minimum weight connected-\(k\)-subgraph cover
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Approximation algorithm for minimum connected 3-path vertex cover
• Approximation algorithms for minimum weight connected 3-path vertex cover
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs

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

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