Holiest Minimum-Cost Paths and Flows in Surface Graphs

Jeff Erickson, Kyle Fox, Luvsandondov Lkhamsuren

Let $G$ be an edge-weighted directed graph with $n$ vertices embedded on an orientable surface of genus $g$. We describe a simple deterministic lexicographic perturbation scheme th…