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 (⋅) time per solution and (2) 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.
Listing acyclic orientations of graphs with single and multiple sources / Conte Alessio; Grossi Roberto; Marino Andrea; Rizzi Romeo. - STAMPA. - 9644:(2016), pp. 319-333. (Intervento presentato al convegno 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 tenutosi a Ensenada nel 11/04/2016-15/04/2016) [10.1007/978-3-662-49529-2_24].
Listing acyclic orientations of graphs with single and multiple sources
Grossi Roberto;Marino Andrea;
2016
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 (⋅) time per solution and (2) 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.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
