Maximum st-Flow in Directed Planar Graphs via Shortest Paths

DOI10.1007/978-3-642-45278-9_36MaRDI QIDQ2870049zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, Anna Harutyunyan

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.5823

Mathematics Subject Classification ID

Flows in graphs (05C21) Extremal problems in graph theory (05C35)

Abstract: Minimum cuts have been closely related to shortest paths in planar graphs via planar duality - so long as the graphs are undirected. Even maximum flows are closely related to shortest paths for the same reason - so long as the source and the sink are on a common face. In this paper, we give a correspondence between maximum flows and shortest paths via duality in directed planar graphs with no constraints on the source and sink. We believe this a promising avenue for developing algorithms that are more practical than the current asymptotically best algorithms for maximum st-flow.

Cited in

(3)

• Faster shortest paths in dense distance graphs, with applications
• scientific article; zbMATH DE number 6297748 (Why is no real title available?)
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs

This page was built for publication: Maximum st-Flow in Directed Planar Graphs via Shortest Paths

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