Graph / Orientation (Bibtex)

P304: Enumeration of all acyclic orientation of a graph
Input:
A graph $G = (V, E)$.
Output:
All acyclic orientation of $G$.
Complexity:
$O(N(|V|+|E|))$ total time ($O(|V|(|V|+E|))$ delay) and $O(|V| + |E|)$ space.
Comment:
A acyclic orientation of $G$ is an assignment of directions of each edge such that $G$ is acyclic.
Reference:
[Barbosa1999] (Bibtex)
P174: Enumeration of all $(s, t)$-orientations of a biconnected planar graph
Input:
A biconnected planar graph $G = (V, E)$ and an edge $(s, t)$ in $G$.
Output:
All $(s, t)$-orientations of $G$.
Complexity:
$O(|V|)$ time per solution.
Comment:
Reference:
[Setiawan2011] (Bibtex)
P513: Enumerate all single source orientations of a graph
Input:
A graph $G = (V, E)$ and a vertex $s \in V$.
Output:
All the orientations of $G$, such that $s$ is the only source.
Complexity:
$O(|E|)$ delay with $O(|E|)$ space.
Comment:
Reference:
[Conte2018] (Bibtex)
P514: Enumerate all the acyclic orientations of a graph
Input:
A graph $G=(V, E)$ and a vertex $s \in V$.
Output:
All the acyclic orientations of $G$, such that $s$ is the only source.
Complexity:
$O(|E||V|)$ delay with $O(|E|)$ space.
Comment:
Reference:
[Conte2018] (Bibtex)
P515: Enumerate all the acyclic orientations of a graph
Input:
A graph $G = (V, E)$.
Output:
All acyclic orientations of $G$.
Complexity:
$O(|E|)$ delay with $O(|E|)$ space.
Comment:
Reference:
[Conte2018] (Bibtex)
P516: Enumerate all the cyclic orientations of a graph with a single source
Input:
A graph $G=(V, E)$ and a vertex $s \in V$.
Output:
All the cyclic orientations of $G$, such that $s$ is the only source.
Complexity:
$O(|E|\cdot h + h^3)$ delay with $O(|E|)$ space, where $h$ is the girth of $G$.
Comment:
Reference:
[Conte2018] (Bibtex)
P517: Enumerate all the cyclic orientations of a graph
Input:
A graph $G = (V, E)$.
Output:
All cyclic orientations of $G$.
Complexity:
$\tilde{O}(|E|)$ delay with $O(|E|)$ space.
Comment:
Reference:
[Conte2018] (Bibtex)