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

zbMATH Keywords

approximation algorithmhardnessAPXtopic-connected overlay

Mathematics Subject Classification ID

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)

Online and Approximate Network Construction from Bounded Connectivity Constraints ⋮ A Computational Study of Reduction Techniques for the Minimum Connectivity Inference Problem ⋮ Online and approximate network construction from bounded connectivity constraints ⋮ Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem ⋮ Corrigendum to ``On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ An improved flow-based formulation and reduction principles for the minimum connectivity inference problem ⋮ Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

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