TY - GEN

T1 - Homology flows, cohomology cuts

AU - Chambers, Erin W.

AU - Erickson, Jeff G

AU - Nayyeri, Amir

PY - 2009/11/9

Y1 - 2009/11/9

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - Computational topology

UR - http://www.scopus.com/inward/record.url?scp=70350672583&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350672583&partnerID=8YFLogxK

U2 - 10.1145/1536414.1536453

DO - 10.1145/1536414.1536453

M3 - Conference contribution

AN - SCOPUS:70350672583

SN - 9781605585062

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 273

EP - 281

BT - STOC'09 - Proceedings of the 2009 ACM International Symposium on Theory of Computing

T2 - 41st Annual ACM Symposium on Theory of Computing, STOC '09

Y2 - 31 May 2009 through 2 June 2009

ER -