A note on multiflows and treewidth

DOI10.1007/s00453-007-9129-zzbMath1176.90600OpenAlexW2048256994MaRDI QIDQ834591

Sanjeev Khanna, Chandra Chekuri, F. Bruce Shepherd

Publication date: 27 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9129-z

zbMATH Keywords

treewidthedge-disjoint pathsproduct multicommodity flow

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Approximation algorithms (68W25)

Related Items (4)

Unnamed Item ⋮ Disjoint paths in sparse graphs ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Walking through waypoints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Tangles, tree-decompositions and grids in matroids
• Graph minors. I. Excluding a forest
• Multicommodity flows in planar graphs
• Quickly excluding a planar graph
• An overtraining-resistant stochastic modeling method for pattern recognition
• Graph minors. XVI: Excluding a non-planar graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The geometry of graphs and some of its algorithmic applications
• Measured descent: A new embedding method for finite metrics
• Edge-disjoint paths in Planar graphs with constant congestion
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• The all-or-nothing multicommodity flow problem
• On average distortion of embedding metrics into the line and into L ₁
• Multicommodity flow, well-linked terminals, and routing problems
• Euclidean distortion and the sparsest cut
• Improved approximation algorithms for minimum-weight vertex separators
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Edge-Disjoint Paths in Planar Graphs with Constant Congestion
• Excluded minors, network decomposition, and multicommodity flow
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: A note on multiflows and treewidth