Graph / Subtree (Bibtex)

P475: Enumeration of all 2trees in a graph

Input:

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

Output:

All 2trees in $G$.

Complexity:

Comment:

2tree: a subgraph with $|V|-2$ vertices of $G$ such that it consists of two connected components and has no circuits.

Reference:

[Maxwell1966] (Bibtex)

P468: Enumerate all subtrees in a graph.

Input:

A graph $G$.

Output:

All subtrees in $G$.

Complexity:

Comment:

Reference:

[Char1968] (Bibtex)

P3: Enumeration of all subtrees in an input tree

Input:

A tree $T=(V, E)$.

Output:

All subtrees included in $T$.

Complexity:

$O(|V|)$ delay and $O(|V|)$ space.

Comment:

Reference:

[Ruskey1981] (Bibtex)

P373: Enumeration of all $k$-noded subtrees in a tree

Input:

A tree $T$ and an integer $k$.

Output:

All $k$-noded subtrees in $T$.

Complexity:

Comment:

Reference:

[Hikita1983] (Bibtex)

P2: Enumeration of all $k$-subtrees in a graph

Input:

A graph $G=(V, E)$ and a positive integer $k$.

Output:

All $k$-subtrees included in $G$.

Complexity:

$O(sk)$ total time, $O(k)$ amortized time per solution, and $O(|E|)$ space.

Comment:

$s$ = number of $k$-subtrees in $G$, a $k$-subtree means a connected, acyclic, and edge induced subgraph with $k$ vertices.

Reference:

[Ferreira2011] (Bibtex)

P4: Enumeration of all $k$-subtrees in an input tree

Input:

A tree $T=(V, E)$ and an integer $k$.

Output:

All $k$-subtrees included in $T$.

Complexity:

$O(1)$ delay and $O(|V|)$ space after $O(|V|)$ time preprocessing.

Comment:

A $k$-subtree is a connected, acyclic, and edge induced subgraph with $k$ vertices.

Reference:

[Wasa2012b] (Bibtex)

P199: Enumeration of all $k$-cardinarity subtrees of a tree with $w$ vertices

Input:

An integer $k$ and a tree $T$ with $w$ element, where $k \le w$.

Output:

All subtrees with $k$ vertices of $T$.

Complexity:

$O(Nw^5)$ total time.

Comment:

$N$ is the number of ideals.

Reference:

[Wild2013] (Bibtex)

P376: Enumeration of all induced subtrees in a $k$-degenerate graph

Input:

A $k$-degenerate graph $G = (V, E)$.

Output:

All induced subtrees in $G$.

Complexity:

$O(k)$ amortized time per solution with $O(|V| + |E|)$ space and preprocessing time.

Comment:

Reference:

[Wasa2014] (Bibtex)