TY - GEN
T1 - Homology flows, cohomology cuts
AU - Chambers, Erin W.
AU - Erickson, Jeff
AU - Nayyeri, Amir
PY - 2009
Y1 - 2009
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 -