Meet and merge: approximation algorithms for confluent flows

DOI10.1145/780542.780598MaRDI QIDQ3581299zbMATH OpenOpenAlexFDO

Authors Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram

Publication date 16 August 2010

Published in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Meet and merge: approximation algorithms for confluent flows
• (Almost) Tight bounds and existence theorems for single-commodity confluent flows
• (Almost) tight bounds and existence theorems for confluent flows
• Capacitated Confluent Flows: Complexity and Algorithms
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems

Cited in

(7)

• Polynomial-time algorithms for special cases of the maximum confluent flow problem
• Traffic engineering of management flows by link augmentations on confluent trees
• Meet and merge: approximation algorithms for confluent flows
• Single-Sink Multicommodity Flow with Side Constraints
• Congestion-free rerouting of flows on DAGs
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• Approximation algorithms and hardness of integral concurrent flow

This page was built for publication: Meet and merge: approximation algorithms for confluent flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3581299)