TY - GEN
T1 - Maximum flows and parametric shortest paths in planar graphs
AU - Erickson, Jeff
PY - 2010
Y1 - 2010
N2 - We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G*. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change Ω(n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.
AB - We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G*. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change Ω(n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.
UR - http://www.scopus.com/inward/record.url?scp=77951688425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951688425&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973075.65
DO - 10.1137/1.9781611973075.65
M3 - Conference contribution
AN - SCOPUS:77951688425
SN - 9780898717013
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 794
EP - 804
BT - Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Association for Computing Machinery
T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms
Y2 - 17 January 2010 through 19 January 2010
ER -