Amortized O(|V|)-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs

2014/08/06 by Rui Ferreira, Roberto Grossi, Ferreira, Rui +7 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1408.1265

openalex publication_date 2014/08/06 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the C chordless cycles contained in an undirected graph G = (V,E) takes O(|E|² +|E|⋅ C) time. In this paper we provide an algorithm taking O(|E| + |V |⋅ C) time. We also show how to obtain the same complexity for listing all the P chordless st-paths in G (where C is replaced by P ).

Cited by

• HTG-GCL: Leveraging Hierarchical Topological Granularity from Cellular Complexes for Graph Contrastive Learning
• CellCLAT: Preserving Topology and Trimming Redundancy in Self-Supervised Cellular Contrastive Learning

Related

• Optimal Listing of Cycles and st-Paths in Undirected Graphs
• An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths
• Efficient Enumeration of Chordless Cycles
• Polynomial enumeration of chordless cycles on cyclically orientable graphs
• Listing 6-Cycles