Skip to Main content Skip to Navigation
New interface
Conference papers

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

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|2 + |E| ·C) time. In this paper we provide an algorithm taking Õ(|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).
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Tuesday, May 30, 2017 - 3:06:24 PM
Last modification on : Tuesday, October 25, 2022 - 4:21:57 PM
Long-term archiving on: : Wednesday, September 6, 2017 - 1:51:45 PM


Files produced by the author(s)




Rui Ferreira, Roberto Grossi, Romeo Rizzi, Gustavo Sacomoto, Marie-France Sagot. Amortized Õ(|V|) -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs. 22th Annual European Symposium on Algorithms, Sep 2014, Wroclaw, Poland. pp.418-429, ⟨10.1007/978-3-662-44777-2_35⟩. ⟨hal-01081031⟩



Record views


Files downloads