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

DOI10.1145/1255443.1255444MaRDI QIDQ3546347zbMATH OpenOpenAlexFDO

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

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)

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

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
• The fluid mechanics of liquid democracy
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• 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
• A diameter-revealing proof of the Bondy-Lovász lemma
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• (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)