A note on multiflows and treewidth
From MaRDI portal
Publication:834591
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
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 1
- 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
