Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

DOI10.1109/FOCS.2011.30MaRDI QIDQ5495017zbMATH OpenFDO

Authors Loïc Séguin-Charbonneau, F. Bruce Shepherd

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.30

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Cited in

(10)

• New algorithms for maximum disjoint paths based on tree-likeness
• Maximum edge-disjoint paths in planar graphs with congestion 2
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• Routing in undirected graphs with constant congestion
• New hardness results for routing on disjoint paths
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Maximum weight disjoint paths in outerplanar graphs via single-tree cut approximators

This page was built for publication: Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495017)