Enumerating Cyclic Orientations of a Graph

Abstract : Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the cyclic orientations of an undirected connected graph with n ver-tices and m edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations. We show that the problem is of independent interest from both combinato-rial and algorithmic points of view, and that each cyclic orientation can be listed with˜Owith˜ with˜O(m) delay time. Space usage is O(m) with an additional setup cost of O(n 2) time before the enumeration begins, or O(mn) with a setup cost of˜Oof˜ of˜O(m) time.
Type de document :
Communication dans un congrès
26th International Workshop on Combinatorial Algorithms, IWOCA 2015, 2016, Verona, Italy. 9538, pp.88 - 99, 2015, 〈10.1007/978-3-319-29516-9_8〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01557026
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 5 juillet 2017 - 17:00:03
Dernière modification le : mercredi 11 avril 2018 - 01:56:03
Document(s) archivé(s) le : mardi 23 janvier 2018 - 21:26:43

Fichier

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

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi. Enumerating Cyclic Orientations of a Graph. 26th International Workshop on Combinatorial Algorithms, IWOCA 2015, 2016, Verona, Italy. 9538, pp.88 - 99, 2015, 〈10.1007/978-3-319-29516-9_8〉. 〈hal-01557026〉

Partager

Métriques

Consultations de la notice

99

Téléchargements de fichiers

34