Homology flows, cohomology cuts

Erin W. Chambers, Jeff G Erickson, Amir Nayyeri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s, t)-flow in O(g 7n log 2 n log 2 C) time for integer capacities that sum to C, or in (g log n) O(g)n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.

Original languageEnglish (US)
Title of host publicationSTOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing
Pages273-281
Number of pages9
DOIs
StatePublished - Nov 9 2009
Event41st Annual ACM Symposium on Theory of Computing, STOC '09 - Bethesda, MD, United States
Duration: May 31 2009Jun 2 2009

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other41st Annual ACM Symposium on Theory of Computing, STOC '09
Country/TerritoryUnited States
CityBethesda, MD
Period5/31/096/2/09

Keywords

  • Combinatorial optimization
  • Computational topology

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Homology flows, cohomology cuts'. Together they form a unique fingerprint.

Cite this