A note on multiflows and treewidth

DOI10.1007/S00453-007-9129-ZzbMATH Open1176.90600OpenAlexW2048256994MaRDI QIDQ834591FDOQ834591

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

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

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)

Cites Work

• An overtraining-resistant stochastic modeling method for pattern recognition
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• 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
• Quickly excluding a planar graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Graph minors. I. Excluding a forest
• Euclidean distortion and the sparsest cut (extended abstract)
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Expander flows, geometric embeddings and graph partitioning
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Graph minors. XVI: Excluding a non-planar graph
• Excluded minors, network decomposition, and multicommodity flow
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• Tangles, tree-decompositions and grids in matroids
• The all-or-nothing multicommodity flow problem
• Multicommodity flow, well-linked terminals, and routing problems
• Edge-disjoint paths in planar graphs with constant congestion
• Title not available (Why is that?)
• Title not available (Why is that?)
• On average distortion of embedding metrics into the line and into \(l_1\)
• Improved approximation algorithms for minimum-weight vertex separators
• Title not available (Why is that?)
• Multicommodity flows in planar graphs
• Probabilistic embeddings of bounded genus graphs into planar graphs
• Title not available (Why is that?)
• Edge-disjoint paths in planar graphs with constant congestion
• Title not available (Why is that?)

Cited In (6)

• Disjoint paths in sparse graphs
• A note on integral generalized flows in directed partial 2-trees
• Title not available (Why is that?)
• New algorithms for maximum disjoint paths based on tree-likeness
• Title not available (Why is that?)
• 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)