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

Rui Ferreira 1 Roberto Grossi 1 Romeo Rizzi 2 Gustavo Sacomoto 3, 4 Marie-France Sagot 5, 4
1 DI - Dipartimento di Informatica [Pisa]
2 DIMI - Dipartimento di Matematica e Informatica - Universita Udine
3 Baobab
PEGASE - Département PEGASE [LBBE]
4 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
5 Service d'Epidémiologie et de santé publique
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 metadatas

Cited literature [16 references]  Display  Hide  Download
https://hal.inria.fr/hal-01081031
Contributor : Marie-France Sagot <>
Submitted on : Tuesday, May 30, 2017 - 3:06:24 PM
Last modification on : Thursday, November 21, 2019 - 1:14:06 PM
Long-term archiving on : Wednesday, September 6, 2017 - 1:51:45 PM

File

esa20140_submission_183.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | INRIA | BAMBOO | BIOENVIS | UNIV-LYON1

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

356

Files downloads

661

Contact


archive-ouverte@inria.fr