Complexity and approximation of the connected set-cover problem

DOI10.1007/S10898-011-9726-XzbMATH Open1250.90104OpenAlexW2099799577MaRDI QIDQ453623FDOQ453623

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

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

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)

Cites Work

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

Cited In (14)

• A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Title not available (Why is that?)
• 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
• Connected Set Cover Problem and Its Applications
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• Approximability results for the converse connected \(p\)-centre problem
• 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'
• Title not available (Why is that?)
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Universal approximations for TSP, Steiner tree, and set cover

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)