Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

DOI10.1145/1806689.1806708zbMath1293.05150arXiv1003.5907OpenAlexW2039303552MaRDI QIDQ2875138

Aleksander Mądry

Publication date: 13 August 2014

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

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

zbMATH Keywords

dynamic graph algorithmsmulticommodity flow problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items (10)

Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Distributed distance computation and routing with small messages ⋮ Hardness Results for Structured Linear Systems ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ Deterministic incremental APSP with polylogarithmic update time and stretch ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

This page was built for publication: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms