An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O(m) for acyclic orientations and (O) over tilde (m) for cyclic ones. When just a single source is specified, these delays become O(m center dot n) and O(m center dot h + h(3)), respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case.

Efficient enumeration of graph orientations with sources

Conte, Alessio;Grossi, Roberto;
2018-01-01

Abstract

An orientation of an undirected graph is obtained by assigning a direction to each of its edges. It is called cyclic when a directed cycle appears, and acyclic otherwise. We study efficient algorithms for enumerating the orientations of an undirected graph. To get the full picture, we consider both the cases of acyclic and cyclic orientations, under some rules specifying which nodes are the sources (i.e. their incident edges are all directed outwards). Our enumeration algorithms use linear space and provide new bounds for the delay, which is the maximum elapsed time between the output of any two consecutively listed solutions. We obtain a delay of O(m) for acyclic orientations and (O) over tilde (m) for cyclic ones. When just a single source is specified, these delays become O(m center dot n) and O(m center dot h + h(3)), respectively, where h is the girth of the graph without the given source. When multiple sources are specified, the delays are the same as in the single source case.
2018
Conte, Alessio; Grossi, Roberto; Marino, Andrea; Rizzi, Romeo
File in questo prodotto:
File Dimensione Formato  
OrientationsJOURNAL.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 564.51 kB
Formato Adobe PDF
564.51 kB Adobe PDF Visualizza/Apri

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: https://hdl.handle.net/11568/1075494
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 3
social impact