Listing Acyclic Orientations of Graphs with Single and Multiple Sources - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Listing Acyclic Orientations of Graphs with Single and Multiple Sources

Résumé

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.
Fichier principal
Vignette du fichier
EnumeratingAcyclicOrientations.pdf (470.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01388470 , version 1 (30-05-2017)

Identifiants

Citer

Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi. Listing Acyclic Orientations of Graphs with Single and Multiple Sources. LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Apr 2016, Ensenada, Mexico. pp.319-333, ⟨10.1007/978-3-662-49529-2_24⟩. ⟨hal-01388470⟩

Collections

INRIA INRIA2
99 Consultations
625 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More