A note on the greedy algorithm for the unsplittable flow problem

DOI10.1016/S0020-0190(03)00351-XMaRDI QIDQ1028992zbMATH OpenFDO

Authors Petr Kolman

Publication date 9 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsgraph algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1947047
• A constant factor approximation algorithm for unsplittable flow on paths
• Approximation algorithms for the unsplittable flow problem
• Combinatorial algorithms for the unsplittable flow problem
• Approximation algorithms for single-source unsplittable flow

Cites work

• scientific article; zbMATH DE number 1187149 (Why is no real title available?)
• 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?)
• Approximation algorithms for disjoint paths and related routing and packing problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Cited in

(4)

• A near-linear time constant factor algorithm for unsplittable flow problem on line with bag constraints
• Combinatorial algorithms for the unsplittable flow problem
• On the minimum cost multiple-source unsplittable flow problem
• Disjoint paths in sparse graphs

This page was built for publication: A note on the greedy algorithm for the unsplittable flow problem

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