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 algorithmtreewidthnetwork flowroutingconfluent flow

Mathematics Subject Classification ID

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

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

(14)

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

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)