On the approximability and hardness of minimum topic connected overlay and its special instances
DOI10.1016/J.TCS.2011.12.033zbMATH Open1238.68063OpenAlexW2058702473MaRDI QIDQ418776FDOQ418776
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
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
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)
Cites Work
- The design of approximation algorithms
- Optimization, approximation, and complexity classes
- The clustering matroid and the optimal clustering tree
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Complexity classifications of Boolean constraint satisfaction problems
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Inferring Social Networks from Outbreaks
- Inapproximability results for bounded variants of optimization problems.
- Structure preserving reductions among convex optimization problems
- A linear-time approximation algorithm for the weighted vertex cover problem
- On the power of unique 2-prover 1-round games
- On efficient fixed-parameter algorithms for weighted vertex cover
- The complete optimal stars-clustering-tree problem
- Title not available (Why is that?)
- A new multilayered {PCP} and the hardness of hypergraph vertex cover
- Constructing scalable overlays for pub-sub with many topics
Cited In (10)
- An improved flow-based formulation and reduction principles for the minimum connectivity inference problem
- A generalized algorithm for publish/subscribe overlay design and its fast implementation
- Constructing scalable overlays for pub-sub with many topics
- Online and Approximate Network Construction from Bounded Connectivity Constraints
- A computational study of reduction techniques for the minimum connectivity inference problem
- Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
- Corrigendum to ``On the approximability and hardness of minimum topic connected overlay and its special instances
- Online and approximate network construction from bounded connectivity constraints
- Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
- On the approximability 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)
