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

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)