Optimal Listing of Cycles and St-paths in Undirected Graphs
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Seite 1884--1896. SIAM, (2013)Zusammenfassung
The classical problem of efficiently listing all the simple cycles in a graph has been studied since the early 70s. For a graph with n vertices and m edges, containing η cycles, the most efficient solution was presented by Johnson SIAM J. Computing, 1975 and takes O((η + 1)(m + n)) time. This solution is not optimal for undirected graphs: nevertheless, no theoretical improvements have been proposed in the past decades. We present the first optimal solution to list all the simple cycles in an undirected graph G. Specifically, let C(G) denote the set of all these cycles (|C(G)| = η). For a cycle c ε C(G), let |c| denote the number of edges in c. Our algorithm requires @@@@ time and is asymptotically optimal: Ω(m) time is necessarily required to read G as input, and @@@@ time is required to list the output. We also present the first optimal solution to list all the simple paths from s to t (shortly, st-paths) in an undirected graph G. Let Pst(G) denote the set of st-paths in G and, for an st-path π ε Pst(G), let |π| be the number of edges in π. Our algorithm lists all the st-paths in G optimally in @@@@ time.