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)

Mathematics Subject Classification ID

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

Cited in

(10)

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

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)