Meet and merge: approximation algorithms for confluent flows

DOI10.1016/J.JCSS.2005.09.009MaRDI QIDQ2495396zbMATH OpenOpenAlexFDO

Authors Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram

Publication date 30 June 2006

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2005.09.009

zbMATH Keywords

approximation algorithmsconfluent flowmulti-commodity flownetwork flowrandomizationroundingrouting

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Meet and merge: approximation algorithms for confluent flows
• Approximation Algorithms for the Maximum Concurrent Flow Problem
• Capacitated Confluent Flows: Complexity and Algorithms
• Approximation algorithms and hardness of integral concurrent flow
• A combinatorial approximation algorithm for concurrent flow problem and its application
• Approximation algorithms for the unsplittable flow problem
• scientific article; zbMATH DE number 1947047
• Approximation algorithms for single-source unsplittable flow
• Combinatorial approximation algorithms for generalized flow problems
• Polynomial-time algorithms for special cases of the maximum confluent flow problem

Cites work

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Approximation algorithms for the covering Steiner problem
• Bounded branching process and and/or tree evaluation
• Branching processes
• Broadcasting on trees and the Ising model.
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Designing multi-commodity flow trees
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 1303564 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• Introduction to algorithms
• Maximal Flow Through a Network
• Meet and merge: approximation algorithms for confluent flows
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On the Distribution of the Number of Successes in Independent Trials
• Provisioning a virtual private network: a network design problem for multicommodity flow
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• The directed subgraph homeomorphism problem
• The geometry of graphs and some of its algorithmic applications

Cited in

(9)

• The fluid mechanics of liquid democracy
• 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
• On Mobile Robots Flow In Locally Uniform Networks
• Stochastic unsplittable flows
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• Minmax centered \(k\)-partitioning of trees and applications to sink evacuation with dynamic confluent flows
• Minmax-regret k-sink location on a dynamic tree network with uniform capacities

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 Q2495396)