Graph / Ordering (Bibtex)

P78: Enumeration of all topological sortings of a directed graph

Input:

A directed graph $G =(V, E)$.

Output:

All topological sortings of $G$.

Complexity:

$O(|V| + |E|)$ time per sorting and $O(|V| + |E|)$ space.

Comment:

Reference:

[Knuth1974] (Bibtex)

P385: Enumeration of all topological sortings of a given set in lexicographically

Input:

An $n$-element set $S$.

Output:

All topological sortings of $S$ in lexicographically.

Complexity:

$O(m)$ time per solution(?).

Comment:

Reference:

[Knuth1979] (Bibtex)

P377: Enumeration of all topological sortings of a po set

Input:

A partial order set $P$.

Output:

All topological sortings of $P$.

Complexity:

$O(|P|)$ time per solution.

Comment:

$|P|$ is the number of objects in $P$.

Reference:

[Varol1981] (Bibtex)

P348: Enumeration of all topological sortings in a directed acyclic graph

Input:

A directed graph $G$.

Output:

All topological sortings in $G$.

Complexity:

$O(1)$ amortized time per solution with $O(|G|)$.

Comment:

Linear extensions correspond to topological sortings.

Reference:

[Pruesse1991a] (Bibtex)

P345: Enumeration of all topological sortings

Input:

A graph $G$.

Output:

All topological sortings in $G$.

Complexity:

$O(1)$ amortized time per solution.

Comment:

A topological sorting is also known as a linear extension.

Reference:

[Ruskey1992a] (Bibtex)

P101: Enumeration of all topological sortings

Input:

A directed acyclic graph $D$.

Output:

All topological sortings $D$.

Complexity:

$O(1)$ amortized time per topological sorting and $O(|V|)$ space in addition to the space used for $D$.

Comment:

Linear sortings correspond to topological sortings.

Reference:

[Pruesse1994] (Bibtex)

P330: Enumeration of all linear extensions of a given poset

Input:

A poset $P$.

Output:

All linear extensions of $P$.

Complexity:

$O(1)$ time per solution.

Comment:

Their algorithm is a loop-free algorithm.

Reference:

[Canfield1995] (Bibtex)

P325: Enumeration of all topological sortings of an acyclic directed graph

Input:

An acyclic directed graph $G = (V, E)$.

Output:

All topological sortings of $G$.

Complexity:

$O(|V|N)$ total time and $O(|V||E|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Avis1996] (Bibtex)

P290: Enumeration of all perfect elimination orderings

Input:

A chordal graph $G$.

Output:

All perfect elimination orderings of $G$.

Complexity:

Constant amortized time per solution.

Comment:

Reference:

[Chandran2003] (Bibtex)

P294: Enumeration of all forest extensions of a partially ordered set

Input:

A partially ordered set $P$.

Output:

All forest extensions of $P$.

Complexity:

$O(|E|^2)$ delay and $O(|E||R|)$ space.

Comment:

$E$ is the set of elements. $R$ is the binary relation on $E$.

Reference:

[Szwarcfiter2003b] (Bibtex)

P39: Enumeration of all topological sortings of a directed acyclic graph

Input:

A directed acyclic graph $D$.

Output:

All topological sortings $D$.

Complexity:

$O(1)$ delay per topological sorting.

Comment:

Linear extensions correspond to topological sortings.

Reference:

[Ono2005] (Bibtex)

P175: Enumeration of all realizer of a triangulated planar graph

Input:

A triangulated planar graph $G = (V, E)$.

Output:

All realizer of $G$.

Complexity:

$O(|V|)$ time per realizer.

Comment:

Reference:

[Yamanaka2006] (Bibtex)

P241: Enumeration of all perfect elimination orderings of a chordal graph

Input:

A chordal graph $G = (V, E)$.

Output:

All perfect elimination orderings of $G$.

Complexity:

$O(1)$ time per solution on average with $O(|V|^2)$ space and $O(|V|^3)$ with $O(|V|^2)$ space pre-computation.

Comment:

Reference:

[Matsui2008] (Bibtex)

P38: Enumeration of all perfect sequences in a chordal graph

Input:

A chordal graph $G = (V, E)$.

Output:

All perfect sequences of $G$.

Complexity:

$O(1)$ time per graph with $O(|V|^2)$ space with $O(|V|^3)$ time and $O(|V|^2)$ space pre-computation.

Comment:

Reference:

[Matsui2010] (Bibtex)