Our paper “Listing Acyclic Orientations of Graphs with Single and Multiple Sources” has been accepted to be published at
Latin American Theoretical Informatics Symposium, LATIN 2016 to be held in Ensenada, Mexico (April 11-15, 2016).
The abstract follows.
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(m+n) working space. When no sources are specified, our algorithm improves over previous work by reducing the delay from O(m n) to O(m) time, and is the first ones with linear delay.
Thanks to all my coauthors: Alessio Conte, Roberto Grossi, and Romeo Rizzi.