On the approximability and hardness of minimum topic connected overlay and its special instances

DOI10.1016/j.tcs.2011.12.033zbMath1238.68063MaRDI 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 algorithm; hardness; APX; topic-connected overlay

Mathematics Subject Classification ID

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

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

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