Enumerating cyclic orientations of a graph

DOI10.1007/978-3-319-29516-9_8MaRDI QIDQ2798221zbMATH OpenOpenAlexFDO

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi

Publication date 4 April 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.05977

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

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 emph{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 $ildeO(m)$ delay time. Space usage is $O(m)$ with an additional setup cost of $O(n^2)$ time before the enumeration begins, or $O(mn)$ with a setup cost of $ildeO(m)$ time.

Recommendations

• Efficient enumeration of graph orientations with sources
• Generating all the acyclic orientations of an undirected graph
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Generating the Acyclic Orientations of a Graph
• k-cyclic orientations of graphs

Cited in

(11)

• Enumerating \(k\)-arc-connected orientations
• Generating all the acyclic orientations of an undirected graph
• Efficient enumeration of graph orientations with sources
• Cyclical orientations of graphs
• Enumeration of Golomb rulers and acyclic orientations of mixed graphs
• On cyclically orientable graphs
• Polynomial enumeration of chordless cycles on cyclically orientable graphs
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Directing Road Networks by Listing Strong Orientations
• Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
• k-cyclic orientations of graphs

This page was built for publication: Enumerating cyclic orientations of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2798221)