P501: Enumeration of all connected induced subgraphs of order $k$.

P501: Enumeration of all connected induced subgraphs of order $k$.

Input:

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

Output:

All connected induced subgraphs of order $k$ in $G$.

Complexity:

$O(k^2\Delta)$ delay with $O(|V|+|E|)$ space, where $\Delta$ is the maximum degree.

Comment:

The overall running time is: $O((e(\Delta - 1))^{k-1} (\Delta + k) n/k)$ time.

Reference:

[Komusiewicz2019] (Bibtex)