On the approximability and hardness of minimum topic connected overlay and its special instances
DOI10.1016/j.tcs.2011.12.033zbMath1238.68063OpenAlexW2058702473MaRDI QIDQ418776
Monika Steinová, Jun Hosoda, Hirotaka Ono, Taisuke Izumi, Koichi Wada, Juraj Hromkovič
Publication date: 30 May 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.033
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (7)
Cites Work
- Unnamed Item
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- The clustering matroid and the optimal clustering tree
- The complete optimal stars-clustering-tree problem
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The Design of Approximation Algorithms
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- On the power of unique 2-prover 1-round games
- A new multilayered PCP and the hardness of hypergraph vertex cover
- A linear-time approximation algorithm for the weighted vertex cover problem
- On efficient fixed-parameter algorithms for weighted vertex cover
- Inferring Social Networks from Outbreaks
- Constructing scalable overlays for pub-sub with many topics
- Fundamentals of Computation Theory
This page was built for publication: On the approximability and hardness of minimum topic connected overlay and its special instances