Negative-Weight shortest paths and unit capacity minimum cost flow in Õ(m[superscript 10/7] log W) Time
In this paper, we study a set of combinatorial optimization problems on weighted graphs: the shortest path problem with negative weights, the weighted perfect bipartite matching problem, the unit-capacity minimum-cost maximum flow problem, and the weighted perfect bipartite b-matching problem under...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2018
|
| Online Access: | http://hdl.handle.net/1721.1/113883 https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0003-0536-0323 https://orcid.org/0000-0003-0722-304X |