A note on multiflows and treewidth

DOI10.1007/S00453-007-9129-ZMaRDI QIDQ834591zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Sanjeev Khanna, 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) Approximation algorithms (68W25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Flow-cut gaps for integer and fractional multiflows
• Flow-cut gaps for integer and fractional multiflows
• On routing disjoint paths in bounded treewidth graphs
• scientific article; zbMATH DE number 5899246
• Approximate max-integral-flow/min-multicut theorems

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 1187149 (Why is no real title available?)
• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• scientific article; zbMATH DE number 475614 (Why is no real title available?)
• scientific article; zbMATH DE number 2038727 (Why is no real title available?)
• scientific article; zbMATH DE number 2119660 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• An overtraining-resistant stochastic modeling method for pattern recognition
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Edge-disjoint paths in planar graphs with constant congestion
• Edge-disjoint paths in planar graphs with constant congestion
• Euclidean distortion and the sparsest cut (extended abstract)
• Excluded minors, network decomposition, and multicommodity flow
• Expander flows, geometric embeddings and graph partitioning
• Graph minors. I. Excluding a forest
• Graph minors. XVI: Excluding a non-planar graph
• Improved approximation algorithms for minimum-weight vertex separators
• Measured descent: A new embedding method for finite metrics
• Multicommodity flow, well-linked terminals, and routing problems
• Multicommodity flows in planar graphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On average distortion of embedding metrics into the line and into \(l_1\)
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Probabilistic embeddings of bounded genus graphs into planar graphs
• Quickly excluding a planar graph
• Tangles, tree-decompositions and grids in matroids
• The all-or-nothing multicommodity flow problem
• The geometry of graphs and some of its algorithmic applications

Cited in

(6)

• Disjoint paths in sparse graphs
• A note on integral generalized flows in directed partial 2-trees
• New algorithms for maximum disjoint paths based on tree-likeness
• scientific article; zbMATH DE number 6861995 (Why is no real title available?)
• Randomly coloring graphs of logarithmically bounded pathwidth
• Walking through waypoints

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

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