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

DOI10.1016/j.tcs.2020.05.043zbMath1453.68140OpenAlexW3033259281MaRDI QIDQ2197543

Zhao Zhang, Pengcheng Liu, Xiao-hui Huang

Publication date: 1 September 2020

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

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

zbMATH Keywords

approximation algorithmgirthconnected-\(k\)-subgraph cover

Mathematics Subject Classification ID

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

Related Items (1)

Computing connected-\(k\)-subgraph cover with connectivity requirement

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for minimum (weight) connected \(k\)-path vertex cover
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• 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
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• A faster FPT algorithm for 3-path vertex cover
• A new approach for approximating node deletion problems
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• On approximability of connected path vertex cover
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• Approximation algorithms for minimum weight connected 3-path vertex cover
• Minimum \(k\)-path vertex cover
• The \(k\)-separator problem: polyhedra, complexity and approximation results
• 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
• Node-Deletion NP-Complete Problems
• Partitioning a Graph into Small Pieces with Applications to Path Transversal
• Hitting topological minors is FPT
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• Approximation Schemes via Width/Weight Trade-offs on Minor-free Graphs
• Losing Treewidth by Separating Subsets
• Inapproximability of $H$-Transversal/Packing

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