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

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)