Online and Approximate Network Construction from Bounded Connectivity Constraints

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

zbMATH Keywords

approximation algorithmconnectivityinduced subgraphonline algorithmnetwork optimization

Mathematics Subject Classification ID

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