Graph / Subgraph (Bibtex)

P324: Enumeration of all connected induced subgraph of a graph

Input:

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

Output:

All connected induced subgraph of $G$.

Complexity:

$O(|V||E|N)$ total time and $O(|V| + |E|)$ space.

Comment:

$N$ is the number of solutions.

Reference:

[Avis1996] (Bibtex)

P298: Enumeration of all connected common maximal subgraphs in two graphs

Input:

Two graphs $G$ and $G'$.

Output:

All connected common maximal subgraphs in $G$ and $G'$.

Complexity:

Comment:

Reference:

[Koch2001] (Bibtex)