P439: Enumeration of all maximal $k$-degenerate induced graph in a chordal graph

P439: Enumeration of all maximal $k$-degenerate induced graph in a chordal graph

Input:

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

Output:

All maximal $k$-degenerate induced graphs in $G$.

Complexity:

$O(m\cdot \omega(G)$ time per solution with polynomial space, where $\omega(G)$ is the size of a maximum clique.

Comment:

The number of maximum cliques in a chordal graph is linear in the size of the graph.

Reference:

[Conte2017] (Bibtex)