Capacitated Confluent Flows: Complexity and Algorithms

DOI10.1007/978-3-642-13073-1_31MaRDI QIDQ3563015zbMATH OpenOpenAlexFDO

Authors Daniel Dressler, Martin Strehler

Publication date 28 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13073-1_31

zbMATH Keywords

approximation algorithmconfluent flownetwork flowroutingtreewidth

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• On a capacity scaling algorithm for the constrained maximum flow problem
• A capacity scaling algorithm for the constrained maximum flow problem
• Polynomial-time algorithms for special cases of the maximum confluent flow problem
• scientific article; zbMATH DE number 3982882
• Approximation Algorithms for the Maximum Concurrent Flow Problem
• A capacity scaling algorithm for convex cost submodular flows
• scientific article; zbMATH DE number 3950169
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• Flow trees for vertex-capacitated networks
• A computational study of the capacity scaling algorithm for the maximum flow problem

Cited in

(15)

• Exact solution algorithms for the maximum flow problem with additional conflict constraints
• Minmax regret for sink location on dynamic flow paths with general capacities
• Polynomial-time algorithms for special cases of the maximum confluent flow problem
• Meet and merge: approximation algorithms for confluent flows
• Separable convexification and DCA techniques for capacity and flow assignment problems.
• Capacity-filtering algorithms for finite-capacity planning of a flexible flow line
• The maximum flow problem with conflict and forcing conditions
• Meet and merge: approximation algorithms for confluent flows
• scientific article; zbMATH DE number 1418332 (Why is no real title available?)
• Non-approximability and polylogarithmic approximations of the single-sink unsplittable and confluent dynamic flow problems
• Flows with Unit Path Capacities and Related Packing and Covering 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
• Uncapacitated flow-based extended formulations
• Flow trees for vertex-capacitated networks

This page was built for publication: Capacitated Confluent Flows: Complexity and Algorithms

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