Flows on few paths: Algorithms and lower bounds

DOI10.1002/NET.20121MaRDI QIDQ5487813zbMATH OpenOpenAlexFDO

Authors Maren Martens, Martin Skutella

Publication date 12 September 2006

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20121

zbMATH Keywords

\(k\)-splittable flowapproximation algorithmmulticommodity flownetwork flowrandomized roundingunsplittable flow

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Algorithms – ESA 2004
• Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths
• scientific article; zbMATH DE number 3950169
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Flows, cuts and integral routing in graphs -- an approximation algorithmist's perspective
• Approximation algorithms for the unsplittable flow problem on paths and trees
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow
• scientific article; zbMATH DE number 1751596
• scientific article; zbMATH DE number 1062936
• Multiflows and disjoint paths of minimum total cost

Cites work

• Hardness of the undirected congestion minimization problem
• scientific article; zbMATH DE number 2079393 (Why is no real title available?)
• scientific article; zbMATH DE number 1757944 (Why is no real title available?)
• scientific article; zbMATH DE number 2119660 (Why is no real title available?)
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New hardness results for congestion minimization and machine scheduling

Cited in

(14)

• Flows with unit path capacities and related packing and covering problems
• A matheuristic approach for the quickest multicommodity \(k\)-splittable flow problem
• Single source unsplittable flows with arc-wise lower and upper bounds
• A local search heuristic for the multi-commodity k-splittable maximum flow problem
• Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths
• K-splittable delay constrained routing problem: A branch-and-price approach
• Comparing branch-and-price algorithms for the multi-commodity k-splittable maximum flow problem
• scientific article; zbMATH DE number 1947385 (Why is no real title available?)
• scientific article; zbMATH DE number 1775441 (Why is no real title available?)
• Single source unsplittable flows with arc-wise lower and upper bounds
• Algorithms – ESA 2004
• Flows with Unit Path Capacities and Related Packing and Covering Problems
• A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem
• An exact approach for the maximum concurrent \(k\)-splittable flow problem

This page was built for publication: Flows on few paths: Algorithms and lower bounds

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