Minimum-cost single-source 2-splittable flow

DOI10.1016/j.ipl.2004.12.009zbMath1182.68362OpenAlexW2107700597MaRDI QIDQ1041715

Stavros G. Kolliopoulos

Publication date: 4 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.12.009

zbMATH Keywords

analysis of algorithmsgraph algorithmsapproximation algorithmsmaximum flowunsplittable flow

Mathematics Subject Classification ID

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

Related Items (9)

Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds ⋮ A fast heuristic algorithm for the maximum concurrent \(k\)-splittable flow problem ⋮ Comparing branch-and-price algorithms for the multi-commodity \(k\)-splittable maximum flow problem ⋮ A local search heuristic for the multi-commodity \(k\)-splittable maximum flow problem ⋮ An exact approach for the maximum concurrent \(k\)-splittable flow problem ⋮ On the approximation of the single source \(k\)-splittable flow problem ⋮ A Branch and Price algorithm for the \(k\)-splittable maximum flow problem ⋮ Single-source \(k\)-splittable min-cost flows ⋮ Single source unsplittable flows with arc-wise lower and upper bounds

Cites Work

• On the single-source unsplittable flow problem
• An approximation algorithm for the generalized assignment problem
• Approximating disjoint-path problems using packing integer programs
• Approximating the single source unsplittable min-cost flow problem
• NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
• Approximation Algorithms for Single-Source Unsplittable Flow

This page was built for publication: Minimum-cost single-source 2-splittable flow