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

DOI10.1016/j.tcs.2014.03.026zbMath1417.68167OpenAlexW2148485937MaRDI QIDQ2447765

Yishuo Shi, Zhao Zhang, Yaping 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 theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover ⋮ Unnamed Item ⋮ Approximation Algorithm for the Minimum Connected $$k$$-Path Vertex Cover Problem ⋮ Computing connected-\(k\)-subgraph cover with connectivity requirement ⋮ 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 ⋮ Kernels for packing and covering problems ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs

Cites Work

• Unnamed Item
• Design and analysis of approximation algorithms
• 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
• Local ratio with negative weights.
• On the hardness of approximating minimum vertex cover
• A unified approximation algorithm for node-deletion problems
• 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
• A 2-approximation algorithm for the vertex coverP₄problem in cubic graphs
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A unified approach to approximating resource allocation and scheduling

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