(Almost) Tight bounds and existence theorems for single-commodity confluent flows
DOI10.1145/1255443.1255444zbMATH Open1311.90017OpenAlexW1995031698MaRDI QIDQ3546347FDOQ3546347
Authors: Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta, Robert D. Kleinberg, László Lovász 
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
Recommendations
- Monotonicity and conformality in multicommodity network‐flow problems
- Equilibrium flow assignment in a single-commodity network
- On methods for the convex multi-commodity flow problem
- Single-Sink Multicommodity Flow with Side Constraints
- Approximating fractional multicommodity flow independent of the number of commodities
- Short proofs on multicommodity flows and cuts
- On the solitaire cone and its relationship to multi-commodity flows.
- (Almost) tight bounds and existence theorems for confluent flows
- scientific article; zbMATH DE number 508835
- Multicommodity flows over time: Efficient algorithms and complexity
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)
Cited In (21)
- Treewidth of graphs with balanced separations
- Congestion-free rerouting of flows on DAGs
- Stochastic unsplittable flows
- The inapproximability of maximum single-sink unsplittable, priority and confluent flow problems
- Traffic engineering of management flows by link augmentations on confluent trees
- Minmax regret for sink location on dynamic flow paths with general capacities
- Meet and merge: approximation algorithms for confluent flows
- Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
- The fluid mechanics of liquid democracy
- Maximum edge-disjoint paths in planar graphs with congestion 2
- The Klein bottle and multicommodity flows
- Polynomial-time algorithms for special cases of the maximum confluent flow problem
- Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
- A diameter-revealing proof of the Bondy-Lovász lemma
- (Almost) tight bounds and existence theorems for confluent flows
- Spanning tree congestion and computation of generalized Győri-Lovász partition
- A Survey on Spanning Tree Congestion
- Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
- Simple undirected two-commodity integral flow with a unitary demand
- A branch-and-bound algorithm for building optimal data gathering tree in wireless sensor networks
- Cluster before you hallucinate: node-capacitated network design and energy efficient routing
This page was built for publication: (Almost) Tight bounds and existence theorems for single-commodity confluent flows
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546347)
