Edge-Disjoint Paths in Planar Graphs with Constant Congestion
From MaRDI portal
Publication:5189546
DOI10.1137/060674442zbMath1185.68848OpenAlexW2024972568MaRDI QIDQ5189546
Chandra Chekuri, F. Bruce Shepherd, Sanjeev Khanna
Publication date: 17 March 2010
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.966.6469
Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Related Items
A note on multiflows and treewidth, All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs, Euclidean prize-collecting Steiner forest, Single-Sink Multicommodity Flow with Side Constraints, Linearity of grid minors in treewidth with applications through bidimensionality, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor, Improved Guarantees for Vertex Sparsification in Planar Graphs, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, Unnamed Item, Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators, A node-capacitated Okamura-Seymour theorem, Routing in Undirected Graphs with Constant Congestion, Unnamed Item
