# Maximum st-flow in directed planar graphs via shortest paths

Article · Glencora Borradaile, Anna Harutyunyan

- Archive id: arxiv:1305.5823
- Published: 2013-05-24
- Venue: Lecture notes in computer science
- DOI: https://doi.org/10.1007/978-3-642-45278-9_36
- arXiv: https://arxiv.org/abs/1305.5823
- Citations: 3
- Source URL: https://arxiv.org/abs/1305.5823
- PDF: https://arxiv.org/pdf/1305.5823
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.