Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. (English) Zbl 1293.90057
Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 735-744 (2013).
MSC:
| 90C27 | Combinatorial optimization |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C21 | Flows in graphs |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C38 | Paths and cycles |
