First offline dynamic APSP algorithm for planar digraphs with Õ(√n) update and query time via faster maintenance of dense distance graphs.
Italiano, Yahav Nussbaum, Piotr Sankowski , and Christian Wulff-Nilsen
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
Presents a successive shortest paths scaling algorithm for unit-capacity min-cost flow achieving Õ((nm)^{2/3} log C) time on planar multigraphs via r-divisions and dense distance graphs.
citing papers explorer
-
Min-Cost Flow in Unit-Capacity Planar Graphs
Presents a successive shortest paths scaling algorithm for unit-capacity min-cost flow achieving Õ((nm)^{2/3} log C) time on planar multigraphs via r-divisions and dense distance graphs.