Fetching the paper…
Reading the bibliography…
In this paper we give an $\widetilde{O}((nm)^{2/3}\log C)$ time algorithm for computing min-cost flow (or min-cost circulation) in unit capacity planar multigraphs where edge costs are integers bounded by $C$.
Constructing maximal dynamic flows from static flows
L. R. Ford and D. R. Fulkerson · 1958
Earlier work this paper cites.
A procedure for determining a family of minimum-cost network flow patterns
Robert G Busacker and Paul J Gowen · 1960
Earlier work this paper cites.
A new method of solving transportation-network problems
Masao Iri · 1960
Earlier work this paper cites.
Optimal flow through networks with gains
William S. Jewell · 1962
Earlier work this paper cites.
Finite graphs and networks: An introduction with applications
Thomas L Saaty and Robert G Busacker · 1965
Earlier work this paper cites.
Algorithm 360: shortest-path forest with topological ordering [H]
Robert B. Dial · 1969
Earlier work this paper cites.
On some techniques useful for solution of transportation network problems
Nobuaki Tomizawa · 1971
Earlier work this paper cites.
Theoretical improvements in algorithmic efficiency for network flow problems
Jack Edmonds and Richard M. Karp · 1972
Earlier work this paper cites.
An n 5/2 {}^{\mbox{5/2}} algorithm for maximum matchings in bipartite graphs
John E. Hopcroft and Richard M. Karp · 1973
Earlier work this paper cites.
Network flow and testing graph connectivity
Shimon Even and Robert Endre Tarjan · 1975
Earlier work this paper cites.
A strongly polynomial minimum cost circulation algorithm
Éva Tardos · 1985
Earlier work this paper cites.
Geometric applications of a matrix-searching algorithm
Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber · 1987
Earlier work this paper cites.
Relaxation methods for minimum cost ordinary and generalized network flow problems
Dimitri P. Bertsekas and Paul Tseng · 1988
Earlier work this paper cites.
A faster strongly polynominal minimum cost flow algorithm
James B. Orlin · 1988
Cited alongside, same era.
Faster scaling algorithms for network problems
Harold N. Gabow and Robert Endre Tarjan · 1989
Cited alongside, same era.
Finding minimum-cost circulations by successive approximation
Andrew V. Goldberg and Robert E. Tarjan · 1990
Cited alongside, same era.
Flow in planar graphs with multiple sources and sinks
Gary L. Miller and Joseph Naor · 1995
Cited alongside, same era.
Planar graphs, negative weight edges, shortest paths, and near linear time
Jittat Fakcharoenphol and Satish Rao · 2005
Cited alongside, same era.
Multiple-source shortest paths in planar graphs
Philip N. Klein · 2005
Cited alongside, same era.
Path finding methods for linear programming: Solving linear programs in õ(vrank) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Later among the works it cites.
Network flow problems in planar graphs
Yahav Nussbaum · 2014
Later among the works it cites.
Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen · 2017
Later among the works it cites.
Negative-weight shortest paths and unit capacity minimum cost flow in õ ( m 10/7 {}^{\mbox{10/7}} log W ) time (extended abstract)
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu · 2017
Later among the works it cites.
Hybrid bellman-ford-dijkstra algorithm
Yefim Dinitz and Rotem Itzhak · 2017
Later among the works it cites.
Minimum-cost flows in unit-capacity networks
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Faster approximate lossy generalized flow via interior point algorithms
Samuel I. Daitch and Daniel A. Spielman · 2008
Cited alongside, same era.
An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
Glencora Borradaile and Philip N. Klein · 2009
Cited alongside, same era.
Maximum flows and parametric shortest paths in planar graphs
Jeff Erickson · 2010
Cited alongside, same era.
Shortest paths in planar graphs with real lengths in O ( n log 2 {}^{\mbox{2}} n /loglog n ) time
Shay Mozes and Christian Wulff-Nilsen · 2010
Cited alongside, same era.
Improved algorithms for min cut and max flow in undirected planar graphs
Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen · 2011
Cited alongside, same era.
Multiple-source shortest paths in embedded graphs
Sergio Cabello, Erin W. Chambers, and Jeff Erickson · 2013
Cited alongside, same era.
Andrew V. Goldberg, Sagi Hed, Haim Kaplan, and Robert E. Tarjan · 2017
Later among the works it cites.
Decremental single-source reachability in planar digraphs
Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski · 2017
Later among the works it cites.
A faster algorithm for minimum-cost bipartite perfect matching in planar graphs
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, and Sharath Raghvendra · 2018
Later among the works it cites.
Improved bounds for shortest paths in dense distance graphs
Pawel Gawrychowski and Adam Karczmarz · 2018
Later among the works it cites.
Decremental transitive closure and shortest paths for planar digraphs and beyond
Adam Karczmarz · 2018
Later among the works it cites.
NC algorithms for weighted planar perfect matching and related problems
Piotr Sankowski · 2018
Later among the works it cites.
A faster algorithm for minimum-cost bipartite matching in minor-free graphs
Nathaniel Lahn and Sharath Raghvendra · 2019
Closest in time.