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.
Title resolution pending
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3verdicts
UNVERDICTED 3representative citing papers
A condensed time-expanded network with O(n²μ) nodes and O(μmn) edges solves max flow over time with μ capacity changes in O(μ²n³m) time.
Regional fulfillment networks reduce order delays relative to global ones when assignments reach equilibrium under a greedy strategy.
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.
-
Brief announcement: A special case of maximum flow over time with network changes
A condensed time-expanded network with O(n²μ) nodes and O(μmn) edges solves max flow over time with μ capacity changes in O(μ²n³m) time.
-
Improved Speed via Regional Fulfillment
Regional fulfillment networks reduce order delays relative to global ones when assignments reach equilibrium under a greedy strategy.