| — Turkish proverb (2009) | |||||||||||||||
Abstract | |||||||||||||||
| We describe the first algorithms to compute minimum cuts in surface-embedded graphs in nearlinear time. Given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, our algorithm computes a minimum (s, t)-cut in g O(g) n log n time. Except for the special case of planar graphs, for which O(n log n)-time algorithms have been known for more than 20 years, the best previous time bounds for finding minimum cuts in embedded graphs follow from algorithms for general sparse graphs. A slight generalization of our minimum-cut algorithm computes a minimum-cost subgraph in every � 2-homology class. We also prove that finding a minimum-cost subgraph homologous to a single input cycle is NP-hard. Bin ölç, bir kes. [Measure a thousand times, cut once.] | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||