Maximum \(k\)-splittable \(s, t\)-flows

DOI10.1007/s00224-007-9068-8zbMath1140.68072OpenAlexW2086260323MaRDI QIDQ927403

Ronald Koch, Ines Spenke, Martin Skutella

Publication date: 6 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9068-8

zbMATH Keywords

Bounded treewidthPolynomial time approximation scheme

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (3)

Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds ⋮ A local search heuristic for the multi-commodity \(k\)-splittable maximum flow problem ⋮ Single source unsplittable flows with arc-wise lower and upper bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short length Menger's theorem and reliable optical routing
• The \(k\)-splittable flow problem
• Complexity and approximability of \(k\)-splittable flows
• An overtraining-resistant stochastic modeling method for pattern recognition
• On the complexity of vertex-disjoint length-restricted path problems
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Mathematical Foundations of Computer Science 2003
• Algorithms for Fault‐Tolerant Routing in Circuit‐Switched Networks
• Algorithms – ESA 2004
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Maximum \(k\)-splittable \(s, t\)-flows