Disjoint paths in sparse graphs
type: Item
instance of: scholarly article
title: Disjoint paths in sparse graphs
zbMATH Open document ID: 1227.05232
author: Cédric Bentz
published in: Discrete Applied Mathematics
publication date: 2010-04-28T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5702670
zbMATH Keywords: disjoint paths
zbMATH Keywords: approximation algorithms
zbMATH Keywords: polynomial-time solvability
zbMATH Keywords: planar graphs
zbMATH Keywords: bounded tree-width
MaRDI profile type: Publication
full work available at URL: j.dam.2009.03.009
OpenAlex ID: W1971175938
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Approximation algorithms for disjoint paths and related routing and packing problems
cites work: On the complexity of the multicut problem in bounded tree-width graphs and digraphs
cites work: Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
cites work: On the complexity of embedding planar graphs to minimize certain distance measures
cites work: Q4734761
cites work: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Q4471352
cites work: Q3002769
cites work: Edge-disjoint paths in Planar graphs with constant congestion
cites work: Multicommodity flow, well-linked terminals, and routing problems
cites work: A note on multiflows and treewidth
cites work: The Complexity of Multiterminal Cuts
cites work: Q4393480
cites work: Q4779157
cites work: On the Complexity of Timetable and Multicommodity Flow Problems
cites work: Maximal Flow Through a Network
cites work: Q3972951
cites work: Edge-disjoint paths in planar graphs
cites work: Edge-disjoint paths in expander graphs
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: The planar multiterminal cut problem
cites work: Q4231910
cites work: Approximations for the disjoint paths problem in high-diameter planar networks
cites work: Q3840354
cites work: A note on the greedy algorithm for the unsplittable flow problem
cites work: Q4828931
cites work: A fast algorithm for maximum integral two-commodity flow in planar graphs
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Eulerian disjoint paths problem in grid graphs is NP-complete
cites work: On the complexity of the disjoint paths problem
cites work: The edge-disjoint paths problem is NP-complete for series-parallel graphs
cites work: Approximate max-integral-flow/min-multicut theorems
cites work: Multicommodity flows in planar graphs
cites work: Probabilistic construction of deterministic algorithms: approximating packing integer programs
cites work: Edge Disjoint Paths in Moderately Connected Graphs
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
DOI: 10.1016/J.DAM.2009.03.009
description: scientific article; zbMATH DE number 5702670