On the approximability and hardness of minimum topic connected overlay and its special instances
From MaRDI portal
Publication:418776
DOI10.1016/j.tcs.2011.12.033zbMath1238.68063MaRDI QIDQ418776
Juraj Hromkovič, Hirotaka Ono, Taisuke Izumi, Monika Steinová, Jun Hosoda, Koichi Wada
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
68M10: Network design and communication in computer systems
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
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
