Disjoint paths in sparse graphs
From MaRDI portal
Publication:967419
DOI10.1016/J.DAM.2009.03.009zbMath1227.05232OpenAlexW1971175938MaRDI QIDQ967419
Publication date: 28 April 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.03.009
Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (2)
Efficient reassembling of three-regular planar graphs ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- On the complexity of embedding planar graphs to minimize certain distance measures
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Improved bounds for the max-flow min-multicut ratio for planar and \(K_{r,r}\)-free graphs
- A note on multiflows and treewidth
- On the complexity of the multicut problem in bounded tree-width graphs and digraphs
- A note on the greedy algorithm for the unsplittable flow problem
- Edge-disjoint paths in planar graphs
- Probabilistic construction of deterministic algorithms: approximating packing integer programs
- The planar multiterminal cut problem
- Multicommodity flows in planar graphs
- Approximations for the disjoint paths problem in high-diameter planar networks
- A fast algorithm for maximum integral two-commodity flow in planar graphs
- Eulerian disjoint paths problem in grid graphs is NP-complete
- Graph minors. XIII: The disjoint paths problem
- On the complexity of the disjoint paths problem
- Edge-Disjoint Paths in Expander Graphs
- Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
- Edge-disjoint paths in Planar graphs with constant congestion
- Maximal Flow Through a Network
- Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
- Approximate max-integral-flow/min-multicut theorems
- Multicommodity flow, well-linked terminals, and routing problems
- Graph minors. II. Algorithmic aspects of tree-width
- On the Complexity of Timetable and Multicommodity Flow Problems
- Approximation algorithms for NP-complete problems on planar graphs
- The Complexity of Multiterminal Cuts
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
- Edge Disjoint Paths in Moderately Connected Graphs
- Graph-Theoretic Concepts in Computer Science
- The edge-disjoint paths problem is NP-complete for series-parallel graphs
This page was built for publication: Disjoint paths in sparse graphs
