Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
From MaRDI portal
Publication:5171158
DOI10.1109/FOCS.2009.28zbMath1292.05251MaRDI QIDQ5171158
Publication date: 25 July 2014
Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (15)
Metric extension operators, vertex sparsifiers and Lipschitz extendability ⋮ Terminal embeddings ⋮ Capacity-preserving subgraphs of directed flow networks ⋮ Vertex Sparsification in Trees ⋮ On mimicking networks representing minimum terminal cuts ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ An improved approximation algorithm for requirement cut ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points
This page was built for publication: Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
