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
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
Gives O(Δ log^{3/2} n) approximation for spanning tree congestion using a new Ω(hb(G)/Δ) lower bound based on hereditary bisection width.
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.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
-
Approximation of Spanning Tree Congestion using Hereditary Bisection
Gives O(Δ log^{3/2} n) approximation for spanning tree congestion using a new Ω(hb(G)/Δ) lower bound based on hereditary bisection width.