Graph / Connected (Bibtex)

P492: Enumeration of all minimal 2-vertex connected graphs with $n$ vertices

Input:

An integer $n$.

Output:

All minimal 2-vertex connected graphs

Complexity:

Comment:

Reference:

[Read1987] (Bibtex)

P129: Enumeration of all minimal strongly connected subgraphs in a strongly connected subgraph

Input:

A strongly connected subgraph $G$.

Output:

All minimal strongly connected subgraph.

Complexity:

Incremental polynomial time.

Comment:

Reference:

[Boros2004b] (Bibtex)

P131: Enumeration of all minimal 2-vertex connected spanning subgraphs in a graph

Input:

A graph $G$.

Output:

All minimal 2-vertex connected spanning subgraphs of $G$.

Complexity:

Incremental polynomial time.

Comment:

Reference:

[Khachiyan2006a] (Bibtex)

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)