Complexity and approximation of the connected set-cover problem

DOI10.1007/S10898-011-9726-XMaRDI QIDQ453623zbMATH OpenOpenAlexFDO

Authors Wei Zhang, Weili Wu, Du Ding-Zhu, Wonjun Lee

Publication date 27 September 2012

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-011-9726-x

zbMATH Keywords

computational complexityapproximation algorithmsconnected set-cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• Complexity and Approximation Results for the Connected Vertex Cover Problem
• Connected Set Cover Problem and Its Applications
• Approximating node connectivity problems via set covers
• scientific article; zbMATH DE number 1670542
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Approximation algorithms for minimum weight partial connected set cover problem
• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets
• Complexity and approximability of the cover polynomial
• Set-cover approximation

Cites work

• A Greedy Heuristic for the Set-Covering Problem
• A threshold of ln n for approximating set cover
• Connected Set Cover Problem and Its Applications
• Polylogarithmic inapproximability

Cited in

(14)

• Universal approximations for TSP, Steiner tree, and set cover
• A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• scientific article; zbMATH DE number 6815827 (Why is no real title available?)
• Computational complexity of the problem of approximation by graphs with connected components of bounded size
• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• Approximability results for the converse connected \(p\)-centre problem
• Connected Set Cover Problem and Its Applications
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• A simple approximation algorithm for minimum weight partial connected set cover
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs

This page was built for publication: Complexity and approximation of the connected set-cover problem

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