Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1166–1176, 2011.

Abstract:

LetGbe a directed graph with weighted edges, embedded on a surface of genusgwithbboundaries. We describe an algorithm to compute the shortest directed cycle inGin any givenZ_{2}-homology class in 2^{O(g+b)}nlogntime; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute the shortest non-separating directed cycle inGin 2^{O(g+b)}nlogntime, improving the recent algorithm of Cabello et al. [SOCG 2010] for allg=o(logn). The second is a combinatorial algorithm to compute minimum (s,t)-cuts inundirectedsurface graphs in 2^{O(g)}nlogntime, improving an algorithm of Chambers et al. [SOCG 2009] for all positiveg. 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.Z_{2}-homology cover

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012