Approximations for the disjoint paths problem in high-diameter planar networks

DOI10.1006/jcss.1998.1579zbMath0912.68151OpenAlexW2081008200MaRDI QIDQ1273862

Éva Tardos, Jon M. Kleinberg

Publication date: 6 January 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/9003

zbMATH Keywords

planar graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Related Items

The disjoint paths problem in quadratic time ⋮ Unnamed Item ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Approximation algorithms for time-constrained scheduling on line networks ⋮ Disjoint paths in sparse graphs ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators ⋮ Routing in Undirected Graphs with Constant Congestion ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-disjoint paths in planar graphs
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Multicommodity flows in planar graphs
• Constructing disjoint paths on expander graphs
• On the complexity of the disjoint paths problem
• Efficient routing in all-optical networks
• Matroid Intersection
• Disjoint Common Transversals and Exchange Structures
• Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover
• Minimum partition of a matroid into independent subsets