Homology flows, cohomology cuts Export

@inproceedings{citeulike:4747181, 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 7 n 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.}, address = {New York, NY, USA}, author = {Chambers, Erin W. and Erickson, Jeff and Nayyeri, Amir}, booktitle = {STOC '09: Proceedings of the 41st annual ACM symposium on Symposium on theory of computing}, citeulike-article-id = {4747181}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1536414.1536453}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1536414.1536453}, doi = {10.1145/1536414.1536453}, isbn = {978-1-60558-506-2}, keywords = {algorithms, graph, optimization, topology}, location = {Bethesda, MD, USA}, pages = {273--282}, posted-at = {2009-06-05 07:37:32}, priority = {2}, publisher = {ACM}, title = {Homology flows, cohomology cuts}, url = {http://dx.doi.org/10.1145/1536414.1536453}, year = {2009} }

TY - CONF ID - citeulike:4747181 L3 - citeulike-article-id:4747181 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 7 n 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. CY - Bethesda, MD, USA SN - 978-1-60558-506-2 AD - New York, NY, USA EP - 282 TI - Homology flows, cohomology cuts PB - ACM T2 - STOC '09: Proceedings of the 41st annual ACM symposium on Symposium on theory of computing SP - 273 KW - algorithms KW - graph KW - optimization KW - topology AU - Chambers, Erin AU - Erickson, Jeff AU - Nayyeri, Amir PY - 2009/// UR - http://dx.doi.org/10.1145/1536414.1536453 ER -