Graph / Tree (Bibtex)

P388: Enumeration of all binary trees with fixed number leaves in lexicographically

Input:

An integer $n$.

Output:

All binary trees with $n$ leaves in lexicographically.

Complexity:

$O(1)$ time per binary tree.

Comment:

Reference:

[Ruskey1977] (Bibtex)

P389: Enumeration of all $t$-ary trees with fixed number leaves in lexicographically

Input:

An integer $n$.

Output:

All $t$-ary trees with $n$ leaves in lexicographically.

Complexity:

$O(t)$ time per binary tree.

Comment:

Reference:

[Ruskey1978a] (Bibtex)

P400: Enumeration of all $k$-ary trees with $n$ vertices

Input:

Integers $k$ and $n$.

Output:

All $k$-ary trees with $n$ vertices

Complexity:

$O(1)$ time per solution

Comment:

Reference:

[Trojanowski1978] (Bibtex)

P402: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Rotem1978a] (Bibtex)

P397: Enumeration of all $k$-ary trees with $n$ vertices

Input:

Integers $k$ and $n$.

Output:

All $k$-ary trees with $n$ vertices

Complexity:

Comment:

Reference:

[Zaks1979] (Bibtex)

P378: Enumeration of all rooted trees with $n$ vertices

Input:

An integer $n$.

Output:

All rooted trees with $n$ vertices.

Complexity:

$O(1)$ amortized time per solution.

Comment:

Reference:

[Beyer1980] (Bibtex)

P379: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Proskurowski1980] (Bibtex)

P384: Enumeration of all $k$-ary trees in lexicographically

Input:

An integer $n$.

Output:

All $k$-ary trees with $n$ internal vertices in lexicographically

Complexity:

$O(1- (k-1)^{k-1}/k^k)^{-1}$ time per solution. This limit is $4/3$ for the binary case.

Comment:

Reference:

[Zaks1980] (Bibtex)

P442: Enumeration of all (rooted) trees with $n$ vertices

Input:

An integer $n$.

Output:

Enumeration of all (rooted) trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Knop1981] (Bibtex)

P374: Enumeration of all regular $k$-ary trees with $n$ ndoes

Input:

Integers $k$ and $n$.

Output:

All regular $k$-ary trees with $n$ ndoes.

Complexity:

Comment:

Reference:

[Zaks1982] (Bibtex)

P443: Enumeration of all ordered trees isomorphic to a given rooted tree.

Input:

A rooted tree $T$.

Output:

All ordered trees isomorphic to $T$.

Complexity:

Comment:

Reference:

[Schultz1982] (Bibtex)

P358: Enumeration of all binary trees with $n$ vertices in the lexicographic ordering

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices in the lexicographic ordering

Complexity:

$O(1)$ time per solution on average.

Comment:

Reference:

[Zerling1985] (Bibtex)

P363: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

$O(n)$ time per solution.

Comment:

Reference:

[Proskurowski1985] (Bibtex)

P365: Enumeration of all ordered trees with $n$ internal vertices

Input:

An integer $n$.

Output:

All ordered trees with $n$ internal vertices.

Complexity:

Comment:

Reference:

[Er1985] (Bibtex)

P357: Enumeration of all free trees with $n$ vertices

Input:

An integer $n$.

Output:

All free trees with $n$ vertices.

Complexity:

$O(1)$ time per solution.

Comment:

Reference:

[Wright1986] (Bibtex)

P480: Enumeration of all binary trees with $n$ internal nodes

Input:

An integer $n$.

Output:

All binary trees with $n$ internal nodes.

Complexity:

$O(1)$ time per solution on average.

Comment:

Reference:

[Pallo1986] (Bibtex)

P355: Enumeration of all $t$-ary trees with $n$ vertices

Input:

Integers $t$ and $n$.

Output:

All $t$-ary trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Er1987] (Bibtex)

P356: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

$O(1)$ time per solution.

Comment:

Reference:

[Lucas1987] (Bibtex)

P359: Enumeration of all trees with $n$ vertices and $m$ leaves

Input:

Integers $n$ and $m$.

Output:

All trees with $n$ vertices and $m$ leaves

Complexity:

Comment:

Reference:

[Pallo1987] (Bibtex)

P353: Enumeration of all $t$-ary trees in A-order

Input:

Integers $t$ and $n$.

Output:

All $t$-ary trees with $n$ vertices in A-order.

Complexity:

$O(1)$ amortized time per solution.

Comment:

Reference:

[VanBaronaigien1988] (Bibtex)

P488: Enumeration of all $k$-ary trees with $n$ vertices

Input:

Integers $k$ and $n$.

Output:

All $k$-ary trees with $n$ vertices.

Complexity:

$O(1)$ delay.

Comment:

Only use homogenous transpositions.

Reference:

[VanBaronaigien1988] (Bibtex)

P351: Enumeration of all binary trees with $n$ leaves

Input:

An integer $n$.

Output:

All binary trees with $n$ leaves.

Complexity:

$O(1)$ amortized time per solution.

Comment:

A strong Gray code can be listed in constant average time per solution.

Reference:

[Ruskey1990] (Bibtex)

P350: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

$O(1)$ time per solution.

Comment:

A loopless generation algorithm is an algorithm where the amount of computation to go from one object to the next is $O(1)$.

Reference:

[VanBaronaigien1991] (Bibtex)

P344: Enumeration of all $k$-ary trees in natural order

Input:

Two integers $k$ and $n$.

Output:

All $k$-ary trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Er1992] (Bibtex)

P342: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

$O(1)$ delay.

Comment:

Reference:

[Lucas1993] (Bibtex)

P333: Enumeration of all binary trees with $n$ vertices

Input:

An integer $n$.

Output:

All binary trees with $n$ vertices.

Complexity:

Comment:

Reference:

[Bapiraju1994] (Bibtex)

P336: Enumeration of all $k$-ary tree

Input:

An integer $k$.

Output:

All $k$-ary trees.

Complexity:

$O(1)$ delay.

Comment:

Reference:

[Korsh1994] (Bibtex)

P318: Enumeration of all binary trees

Input:

Output:

All binary trees.

Complexity:

$O(1)$ time per tree.

Comment:

Reference:

[Xiang1997] (Bibtex)

P312: Enumeration of all $k$-ary trees with $n$ vertices

Input:

Two integers $k$ and $n$.

Output:

All $k$-ary trees with $n$ vertices.

Complexity:

$O(1)$ delay.

Comment:

Shifts and loopless algorithm.

Reference:

[Korsh1998] (Bibtex)

P149: Enumeration of all rooted plane trees with at most $n$ vertices

Input:

An integer $n$.

Output:

All rooted plane trees with at most $n$ vertices.

Complexity:

$O(1)$ time per tree with $O(n)$ space.

Comment:

A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)

P150: Enumeration of all rooted plane trees with exactly $n$ vertices

Input:

An integer $n$.

Output:

All rooted plane trees with exactly $n$ vertices.

Complexity:

$O(1)$ time per tree with $O(n)$ space.

Comment:

A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)

P151: Enumeration of all rooted plane trees with at most $n$ vertices and the maximum degree $D$

Input:

Integers $n$ and $D$.

Output:

All rooted plane trees with at most $n$ vertices and the maximum degree $D$.

Complexity:

$O(1)$ time per tree with $O(n)$ space.

Comment:

A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)

P152: Enumeration of all rooted plane trees with exactly $n$ vertices and exactly $c$ leaves

Input:

An integer $n$.

Output:

All rooted plane trees with exactly $n$ vertices and exactly $c$ leaves .

Complexity:

$O(n-c)$ time per tree with $O(n)$ space.

Comment:

A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)

P153: Enumeration of all plane trees with exactly $n$ vertices

Input:

An integer $n$.

Output:

All plane trees with exactly $n$ vertices.

Complexity:

$O(n^3)$ time per tree with $O(n)$ space.

Comment:

A \textit{plane tree} is a tree with a left-to-right ordering specified for the children of each vertex.

Reference:

[Nakano2002] (Bibtex)

P154: Enumeration of all rooted trees with at most $n$ vertices

Input:

An integer $n$.

Output:

All rooted tree with at most $n$ vertices.

Complexity:

$O(1)$ time per tree and $O(n)$ space.

Comment:

Reference:

[Nakano2003] (Bibtex)

P289: Enumeration of all $n$-trees

Input:

An integer $n$.

Output:

All $n$-trees.

Complexity:

$O(n^4N)$ total time.

Comment:

Reverse search. $N$ is the number of solutions.

Reference:

[Aringhieri2003] (Bibtex)

P148: Enumeration of all trees with $n$ vertices and $d$ diameter

Input:

Integers $n$ and $d$.

Output:

All trees with $n$ vertices and $d$ diameter.

Complexity:

$O(1)$ time per tree with $O(n)$ space.

Comment:

By using the algorithm for each $d = 2, \dots, n-1$, all trees can be enumerated.

Reference:

[Nakano2004] (Bibtex)

P158: Enumeration of all $c$-tree with at most $v$ vertices and diameter $d$

Input:

Integers $n$ and $d$

Output:

All $c$-tree with at most $v$ vertices and diameter $d$.

Complexity:

$O(1)$ time per tree.

Comment:

A tree is a $c$-tree if each vertex has a color $c \in \{c_1, \dots, c_m\}$.

Reference:

[Nakano2005a] (Bibtex)

P276: Enumeration of all nonisomorphic rooted plane trees with $n$ vertices

Input:

An integer $n$.

Output:

All nonisomorphic rooted plane trees with $n$ vertices.

Complexity:

Constant amortized time per solution.

Comment:

Reference:

[Sawada2006] (Bibtex)

P277: Enumeration of all nonisomorphic free plane trees with $n$ vertices

Input:

An integer $n$.

Output:

All nonisomorphic free plane trees with $n$ vertices.

Complexity:

Constant amortized time per solution.

Comment:

Reference:

[Sawada2006] (Bibtex)

P242: Enumeration of all multitrees satisfying given constraints

Input:

A set $\Sigma$ of labels, a function $val: \Sigma \to \mathbb{Z}^+$, and a feature vector $g$ of level $K$.

Output:

All $(\Sigma, val)$-labeled multitrees $T$ such that $f_K(T) = g$ and $deg(v;T) = val(\ell(v))$ for all vertices $v \in T$.

Complexity:

Comment:

This algorithm is for chemical graphs.

Reference:

[Ishida2008] (Bibtex)

P163: Enumeration of all ordered trees with $n$ vertices and $k$ leaves

Input:

Integers $n$ and $k$.

Output:

All ordered trees with $n$ vertices and $k$ leaves.

Complexity:

$O(1)$ delay and $O(n)$ space.

Comment:

Reference:

[Yamanaka2009a] (Bibtex)

P166: Enumeration of all trees with specified degree sequence

Input:

A degree sequence $D$.

Output:

All trees with $D$.

Complexity:

$O(1)$ time per tree.

Comment:

Reference:

[Nakano2009] (Bibtex)