A note on multiflows and treewidth

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

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• 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
• 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
• On average distortion of embedding metrics into the line and into L ₁
• Improved approximation algorithms for minimum-weight vertex separators
• Multicommodity flows in planar graphs
• Edge-Disjoint Paths in Planar Graphs with Constant Congestion

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)