TY - GEN

T1 - Minimum cuts and shortest non-separating cycles via homology covers

AU - Erickson, Jeff

AU - Nayyeri, Amir

PY - 2011

Y1 - 2011

N2 - Let G be a directed graph with weighted edges, embedded on a surface of genus g. We describe an algorithm to compute a shortest directed cycle in G in any given ℤ2-homology class in 2O(g)n log n time; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute a shortest non-separating directed cycle in G in 2O(g)n log n time, improving the recent algorithm of Cabello et ai [SOCG 2010] for all g = o(log n). The second is a combinatorial algorithm to compute minimum (s, t)-cuts in undirected surface graphs in 2O(g)n log n time, improving on previous combinatorial algorithms, and in particular the recent of Chambers et ai [SOCG 2009], for all g - o(log n). Unlike earlier algorithms for surface graphs that construct and search finite portions of the universal cover, our algorithms use another canonical covering space, called the ℤ2-homology cover.

AB - Let G be a directed graph with weighted edges, embedded on a surface of genus g. We describe an algorithm to compute a shortest directed cycle in G in any given ℤ2-homology class in 2O(g)n log n time; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute a shortest non-separating directed cycle in G in 2O(g)n log n time, improving the recent algorithm of Cabello et ai [SOCG 2010] for all g = o(log n). The second is a combinatorial algorithm to compute minimum (s, t)-cuts in undirected surface graphs in 2O(g)n log n time, improving on previous combinatorial algorithms, and in particular the recent of Chambers et ai [SOCG 2009], for all g - o(log n). Unlike earlier algorithms for surface graphs that construct and search finite portions of the universal cover, our algorithms use another canonical covering space, called the ℤ2-homology cover.

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

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

U2 - 10.1137/1.9781611973082.88

DO - 10.1137/1.9781611973082.88

M3 - Conference contribution

AN - SCOPUS:79955737206

SN - 9780898719932

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1166

EP - 1176

BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011

PB - Association for Computing Machinery

ER -