Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the cyclic orientations of an undirected connected graph with n vertices and m edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations. We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with Õ (m) delay time. Space usage is O(m) with an additional setup cost of O(n2) time before the enumeration begins, or O(mn) with a setup cost of Õ(m) time. © Springer International Publishing Switzerland 2016.

Enumerating cyclic orientations of a graph

RIZZI, ROMEO
2016

Abstract

Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the cyclic orientations of an undirected connected graph with n vertices and m edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations. We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with Õ (m) delay time. Space usage is O(m) with an additional setup cost of O(n2) time before the enumeration begins, or O(mn) with a setup cost of Õ(m) time. © Springer International Publishing Switzerland 2016.
9783319295152
Algorithms; Combinatorial mathematics; Directed graphs, Acyclic orientation; Algorithmic techniques; Directed acyclic graph (DAG); Setup costs; Space usage; Undirected connected graphs; Undirected graph; Vertex set, Graph theory
File in questo prodotto:
File Dimensione Formato  
EnumeratingCyclicOrientations.pdf

solo utenti autorizzati

Tipologia: Versione dell'editore
Licenza: Accesso ristretto
Dimensione 217.38 kB
Formato Adobe PDF
217.38 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/954997
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact