Listing Acyclic Orientations of Graphs with Single and Multiple Sources

Abstract : We study enumeration problems for the acyclic orientations of an undirected graph with n nodes and m edges, where each edge must be assigned a direction so that the resulting directed graph is acyclic. When the acyclic orientations have single or multiple sources specified as input along with the graph, our algorithm is the first one to provide guaranteed bounds, giving new bounds with a delay of O(m⋅n) time per solution and O(n2) working space. When no sources are specified, our algorithm improves over previous work by reducing the delay to O(m), and is the first one with linear delay.
Type de document :
Communication dans un congrès
Evangelos Kranakis ; Gonzalo Navarro ; Edgar Chávez. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Apr 2016, Ensenada, Mexico. Springer, 9644, pp.319-333, Lecture Notes in Computer Science. 〈10.1007/978-3-662-49529-2_24〉
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-01388470
Contributeur : Marie-France Sagot <>
Soumis le : mardi 30 mai 2017 - 13:52:15
Dernière modification le : mercredi 11 avril 2018 - 01:52:27
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 13:59:54

Fichier

EnumeratingAcyclicOrientations...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi. Listing Acyclic Orientations of Graphs with Single and Multiple Sources. Evangelos Kranakis ; Gonzalo Navarro ; Edgar Chávez. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Apr 2016, Ensenada, Mexico. Springer, 9644, pp.319-333, Lecture Notes in Computer Science. 〈10.1007/978-3-662-49529-2_24〉. 〈hal-01388470〉

Partager

Métriques

Consultations de la notice

136

Téléchargements de fichiers

60