Online and Approximate Network Construction from Bounded Connectivity Constraints
From MaRDI portal
Publication:6175211
DOI10.1142/s0129054122500265OpenAlexW4313647352MaRDI QIDQ6175211
Jesper Jansson, Andrzej Lingas, Christos Levcopoulos
Publication date: 18 August 2023
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054122500265
Mathematical programming (90Cxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- On the approximability and hardness of minimum topic connected overlay and its special instances
- Improved approximability and non-approximability results for graph diameter decreasing problems
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
- The clustering matroid and the optimal clustering tree
- Network construction with subgraph connectivity constraints
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The Online Set Cover Problem
- On the power of unique 2-prover 1-round games
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Constructing scalable overlays for pub-sub with many topics
This page was built for publication: Online and Approximate Network Construction from Bounded Connectivity Constraints