A note on multiflows and treewidth
type: Item
instance of: scholarly article
title: A note on multiflows and treewidth
zbMATH Open document ID: 1176.90600
author: Chandra Chekuri
author: Sanjeev Khanna
author: F. Bruce Shepherd
published in: Algorithmica
publication date: 2009-08-27T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5598784
zbMATH Keywords: treewidth
zbMATH Keywords: edge-disjoint paths
zbMATH Keywords: product multicommodity flow
MaRDI profile type: Publication
full work available at URL: s00453-007-9129-z
OpenAlex ID: W2048256994
cites work: Q4273870
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: Euclidean distortion and the sparsest cut
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: The all-or-nothing multicommodity flow problem
cites work: Edge-Disjoint Paths in Planar Graphs with Constant Congestion
cites work: Multicommodity flow, well-linked terminals, and routing problems
cites work: Q3002769
cites work: Edge-disjoint paths in Planar graphs with constant congestion
cites work: Q4449192
cites work: Improved approximation algorithms for minimum-weight vertex separators
cites work: Q3972951
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Tangles, tree-decompositions and grids in matroids
cites work: Cuts, trees and \(\ell_1\)-embeddings of graphs
cites work: Q3602875
cites work: Excluded minors, network decomposition, and multicommodity flow
cites work: An overtraining-resistant stochastic modeling method for pattern recognition
cites work: Q3840354
cites work: Q4828931
cites work: Measured descent: A new embedding method for finite metrics
cites work: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
cites work: The geometry of graphs and some of its algorithmic applications
cites work: Multicommodity flows in planar graphs
cites work: On average distortion of embedding metrics into the line and into L 1
cites work: Graph minors. I. Excluding a forest
cites work: Q3972953
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Quickly excluding a planar graph
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
DOI: 10.1007/S00453-007-9129-Z
description: scientific article; zbMATH DE number 5598784