Max flows in O(nm) time, or better
In this paper, we present improved polynomial time algorithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in O(nm + m[superscript 31/16] log[superscript 2] n) time. In the case that m = O(n[superscript 1.06]), this improves u...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/88020 https://orcid.org/0000-0002-7488-094X |