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 3, 4
1 DI - Dipartimento di Informatica [Pisa]
2 DIMI - Dipartimento di Matematica e Informatica - Universita Udine
3 LBBE - Laboratoire de Biométrie et Biologie Evolutive
4 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive
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).
Type de document :
Communication dans un congrès
22th Annual European Symposium on Algorithms, Sep 2014, Wroclaw, Poland. 8737, pp.418-429, 2014, Algorithms ESA 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44777-2_35〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01081031
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 15:06:24
Dernière modification le : jeudi 19 avril 2018 - 14:49:48
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:51:45

Fichier

esa20140_submission_183.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | BAMBOO | BIOENVIS | UNIV-LYON1 | INRIA-RENGRE

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. 8737, pp.418-429, 2014, Algorithms ESA 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-44777-2_35〉. 〈hal-01081031〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

20

Contact


archive-ouverte@inria.fr