Efficient enumeration of graph orientations with sources

Abstract : An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O(m) for acyclic orientations and ˜Oand˜ and˜O(m) for cyclic ones. When just a single source is specified, these delays become O(m · n) and O(m · h + h 3), respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case. .
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.08.002〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01609009
Contributeur : Marie-France Sagot <>
Soumis le : mardi 3 octobre 2017 - 09:42:04
Dernière modification le : mercredi 11 avril 2018 - 01:59:49

Fichier

1-s2.0-S0166218X1730375X-main....
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi. Efficient enumeration of graph orientations with sources. Discrete Applied Mathematics, Elsevier, 2017, 〈10.1016/j.dam.2017.08.002〉. 〈hal-01609009〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

40