Directed spanners via flow-based linear programs

DOI10.1145/1993636.1993680zbMath1288.68262arXiv1011.3701OpenAlexW2060054375MaRDI QIDQ5419102

Robert Krauthgamer, Michael Dinitz

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.3701

zbMATH Keywords

linear programmingapproximation algorithmsspanners

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Unnamed Item ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Distributed Spanner Approximation ⋮ Unnamed Item ⋮ Distributed Distance-Bounded Network Design Through Distributed Convex Programming ⋮ Lasserre integrality gaps for graph spanners and related problems

This page was built for publication: Directed spanners via flow-based linear programs