Capacitated Confluent Flows: Complexity and Algorithms

DOI10.1007/978-3-642-13073-1_31zbMATH Open1284.68294OpenAlexW1603458698MaRDI QIDQ3563015FDOQ3563015

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

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

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)

Cited In (12)

• The maximum flow problem with conflict and forcing conditions
• Capacity-filtering algorithms for finite-capacity planning of a flexible flow line
• 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.
• Title not available (Why is that?)
• 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)