7768
eng
reportzib
0
--
2020-03-01
--
Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited
In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.
1438-0064
urn:nbn:de:0297-zib-77684
Kai-Helge Becker
Benjamin Hiller
Benjamin Hiller
ZIB-Report
20-05
eng
uncontrolled
acyclic orientations
eng
uncontrolled
enumeration algorithm
eng
uncontrolled
multiple sources and sinks
eng
uncontrolled
bipolar orientations
Computer Applications
COMBINATORICS (For finite fields, see 11Txx)
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Hiller, Benjamin
MODAL-GasLab
MODAL-Gesamt
ECMATH-MI10
https://opus4.kobv.de/opus4-zib/files/7768/ZR-20-05-pdf