(Almost) Tight bounds and existence theorems for single-commodity confluent flows

DOI10.1145/1255443.1255444zbMath1311.90017OpenAlexW1995031698MaRDI QIDQ3546347

Jiangzhuo Chen, László Lovász, Adrian Vetta, Ravi Sundaram, Rajmohan Rajaraman, Robert D. Kleinberg

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1255443.1255444

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Deterministic network models in operations research (90B10) Approximation algorithms (68W25)

Related Items (12)

A Survey on Spanning Tree Congestion ⋮ Minmax regret for sink location on dynamic flow paths with general capacities ⋮ A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks ⋮ The fluid mechanics of liquid democracy ⋮ Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows ⋮ Polynomial-time algorithms for special cases of the maximum confluent flow problem ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Stochastic Unsplittable Flows ⋮ Maximum edge-disjoint paths in planar graphs with congestion 2 ⋮ A diameter-revealing proof of the Bondy-Lovász lemma ⋮ Treewidth of graphs with balanced separations ⋮ Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

This page was built for publication: (Almost) Tight bounds and existence theorems for single-commodity confluent flows