Graph / Cycle (Bibtex)

P427: Enumeration of all cycles in an $n$-cube, where $n \le 4$

Input:

An integer $n$.

Output:

All cycles (closed paths) in an $n$-cube.

Complexity:

Comment:

Reference:

[Gilbert1958] (Bibtex)

P428: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Welch1965] (Bibtex)

P392: Enumeration of all simple cycles in a graph

Input:

A graph $G$.

Output:

All simple cycles in $G$.

Complexity:

Comment:

Reference:

[Ponstein1966] (Bibtex)

P421: Enumeration of all circuits in a graph

Input:

A graph $G$.

Output:

All circuits in $G$.

Complexity:

Comment:

Reference:

[Welch1966] (Bibtex)

P419: Enumeration of all directed circuits in a directed graph

Input:

A directed graph $G$.

Output:

All directed circuits in $G$.

Complexity:

Comment:

Reference:

[Kamae1967] (Bibtex)

P414: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Danielson1968] (Bibtex)

P413: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Rao1969] (Bibtex)

P390: Enumeration of all elementary circuit in a graph

Input:

A graph $G$.

Output:

All elementary circuit in $G$.

Complexity:

Comment:

Reference:

[Tiernan1970] (Bibtex)

P429: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Char1970] (Bibtex)

P406: Enumeration of all cycles in an undirected graph

Input:

An undirected graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Weinblatt1972] (Bibtex)

P412: Enumeration of all cycles in a finite undirected graph

Input:

A finite undirected graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

He claimed that J. T. Welch, Jr.'s algorithm is wrong.

Reference:

[Weinblatt1972] (Bibtex)

P6: Enumeration of all cycles in a directed graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O((|V|\cdot |E|)(C+1))$ total time and $O(|V| + |E|)$ space.

Comment:

$C$ is the number of cycles included in $G$.

Reference:

[Tarjan1973] (Bibtex)

P430: Enumeration of all cycles in a directed graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|E| + c(|V| \times |E|))$ total, where $c$ is the number of circuits in $G$.

Comment:

Reference:

[Ehrenfeucht1973] (Bibtex)

P7: Enumeration of all cycles in a directed graph

Input:

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

Output:

All cycles in $G$.

Complexity:

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

Comment:

$C$ is the number of cycles included in $G$.

Reference:

[Johnson1975] (Bibtex)

P103: Enumeration of all cycles in a graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|E|)$ time per cycle with $O(|E|)$ space.

Comment:

Reference:

[Read1975] (Bibtex)

P104: Enumeration of all cycles in a directed graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|E|)$ time per cycle with $O(|E|)$ space.

Comment:

Reference:

[Read1975] (Bibtex)

P465: Enumerate all directed cycles in a directed graph.

Input:

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

Output:

All directed cycles in $G$.

Complexity:

$O(|V| + |E|(C+1))$ time per solution with $O(|V| + |E|)$ space, where $C$ is the number of solutions.

Comment:

Reference:

[Szwarcfiter1976] (Bibtex)

P440: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Srimani1979] (Bibtex)

P8: Enumeration of all cycles in a planar graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|V|(C+1))$ total time and $O(|V|)$ space.

Comment:

$C$ is the number of cycles included in $G$.

Reference:

[Syso1981] (Bibtex)

P444: Enumeration of all cycles in a directed graph.

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|V| + |E|)$ time per solution.

Comment:

Reference:

[Loizou1982] (Bibtex)

P489: Enumeration of all cycles in a graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|V|^2 \alpha)$ total time with $O(|V|)$ space.

Comment:

Use cycle vectors. Here, $\alpha$ is the number of solutions.

Reference:

[DOGRUSOZ1996] (Bibtex)

P317: Enumeration of all cycles of a given length in a graph

Input:

A graph $G$ and an integer $k$.

Output:

All cycles of length $k$ in $G$.

Complexity:

See paper.

Comment:

Reference:

[Alon1997] (Bibtex)

P243: Enumeration of all cycles in a graph

Input:

A graph $G$.

Output:

All cycles in $G$.

Complexity:

Comment:

Reference:

[Wild2008] (Bibtex)

P244: Enumeration of all small cycles in a graph

Input:

A graph $G$.

Output:

All cycles with length at most $5$ in $G$.

Complexity:

Comment:

Reference:

[Wild2008] (Bibtex)

P245: Enumeration of all chordless cycles in a graph

Input:

A graph $G$.

Output:

All chordless cycles in $G$.

Complexity:

Comment:

Reference:

[Wild2008] (Bibtex)

P5: Enumeration of all cycles in a graph

Input:

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

Output:

All cycles in $G$.

Complexity:

$O(|E| + \sum_{c \in \mathcal{C}(G)}|c|)$ total time.

Comment:

$\mathcal{C}(G)$ is the set of all cycles in $G$.

Reference:

[Ferreira2012] (Bibtex)

P11: Enumeration of all chordless cycles in a graph

Input:

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

Output:

All chordless cycles in $G$.

Complexity:

$\tilde{O}(|E| +|V|\cdot C )$ total time.

Comment:

$C$ is the number of chordless cycles in $G$.

Reference:

[Ferreira2014] (Bibtex)

P12: Enumeration of all chordless cycles in a graph

Input:

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

Output:

All chordless cycles in $G$.

Complexity:

$O(|V|+|E|)$ time per chordless cycle.

Comment:

Reference:

[Unoc] (Bibtex)