Holiest minimum-cost paths and flows in surface graphs

DOI10.1145/3188745.3188904zbMath1428.68322arXiv1804.01045OpenAlexW2964155548MaRDI QIDQ5230385

Kyle Fox, Jeff Erickson, Luvsandondov Lkhamsuren

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.01045

zbMATH Keywords

graphsshortest pathssurfacesnetwork flowscomputational topology

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Flows in graphs (05C21) Computational methods for problems pertaining to algebraic topology (55-08)

Related Items (7)

Minimum Cuts in Surface Graphs ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Topologically trivial closed walks in directed surface graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Unnamed Item ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

This page was built for publication: Holiest minimum-cost paths and flows in surface graphs