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

DOI10.1016/J.TCS.2011.12.033MaRDI QIDQ418776zbMATHOpenAlexFDO

Authors Jun Hosoda, Taisuke Izumi, Hirotaka Ono, Monika Steinová, 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

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Recommendations

• On the approximability of minimum topic connected overlay and its special instances
• Constructing scalable overlays for pub-sub with many topics
• A generalized algorithm for publish/subscribe overlay design and its fast implementation
• Corrigendum to ``On the approximability and hardness of minimum topic connected overlay and its special instances
• Designing Overlapping Networks for Publish-Subscribe Systems

Cites work

• scientific article; zbMATH DE number 1566497 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• A new multilayered {PCP} and the hardness of hypergraph vertex cover
• Complexity classifications of Boolean constraint satisfaction problems
• Constructing scalable overlays for pub-sub with many topics
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Inapproximability results for bounded variants of optimization problems.
• Inferring Social Networks from Outbreaks
• On efficient fixed-parameter algorithms for weighted vertex cover
• On the power of unique 2-prover 1-round games
• Optimization, approximation, and complexity classes
• Structure preserving reductions among convex optimization problems
• The clustering matroid and the optimal clustering tree
• The complete optimal stars-clustering-tree problem
• The design of approximation algorithms
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(10)

• Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
• A computational study of reduction techniques for the minimum connectivity inference problem
• Constructing scalable overlays for pub-sub with many topics
• On the approximability of minimum topic connected overlay and its special instances
• An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
• Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
• Online and approximate network construction from bounded connectivity constraints
• Online and Approximate Network Construction from Bounded Connectivity Constraints
• A generalized algorithm for publish/subscribe overlay design and its fast implementation
• Corrigendum to ``On the approximability and hardness of minimum topic connected overlay and its special instances

This page was built for publication: On the approximability and hardness of minimum topic connected overlay and its special instances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418776)