Optimal Listing of Cycles and st-Paths in Undirected Graphs

2012/05/12 by Ferreira, Rui, Grossi, Roberto, Marino, Andrea +3 · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1205.2766

Abstract

We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time taken to read the input graph plus the time to list the output, namely, the edges in each of the cycles. The algorithm uses a reduction to the problem of listing all the paths from a vertex s to a vertex t which we also solve optimally.

Cited by

• Efficient Temporal Simple Path Graph Generation
• On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs

Related

• Efficiently listing bounded length st-paths
• Efficiently Listing Combinatorial Patterns in Graphs
• Amortized O(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
• Listing 6-Cycles
• Finding Paths and Cycles in Graphs