Graph / Path (Bibtex)

P393: Enumeration of all simple paths in a graph

Input:

A graph $G$.

Output:

All simple paths in $G$.

Complexity:

Comment:

Reference:

[Ponstein1966] (Bibtex)

P420: Enumeration of all directed paths in a directed graph

Input:

A directed graph $G$.

Output:

All directed paths in $G$.

Complexity:

Comment:

Reference:

[Kamae1967] (Bibtex)

P422: Enumeration of all paths in a graph

Input:

A graph $G$.

Output:

All paths in $G$.

Complexity:

Comment:

Reference:

[Kroft1967b] (Bibtex)

P441: Enumeration of all shortest paths between all pairs of vertices in a graph

Input:

A graph $G$.

Output:

Enumeration of all shortest paths between all pairs of vertices $G$

Complexity:

Comment:

Reference:

[Hu1967] (Bibtex)

P415: Enumeration of all paths in a graph

Input:

A graph $G$.

Output:

All paths in $G$.

Complexity:

Comment:

Reference:

[Danielson1968] (Bibtex)

P121: Enumeration of $k$ shortest paths in a graph

Input:

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

Output:

$K$ shortest paths in $G$.

Complexity:

$O(|V|^3)$ total time.

Comment:

Reference:

[Yen1971] (Bibtex)

P79: Enumeration of $k$ shortest paths in a graph

Input:

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

Output:

$k$ shortest paths in $G$.

Complexity:

$O(k|V|c(|V|))$ total time.

Comment:

(?) $c(n)$ is the time complexity to find an optimal solution to a problem with $n$ (0, 1) variables.

Reference:

[Lawler1972] (Bibtex)

P105: Enumeration of all paths in a graph

Input:

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

Output:

All paths in $G$.

Complexity:

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

Comment:

Reference:

[Read1975] (Bibtex)

P106: Enumeration of all paths in a directed graph

Input:

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

Output:

All paths in $G$.

Complexity:

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

Comment:

Reference:

[Read1975] (Bibtex)

P109: Enumeration of $k$ shortest paths in a graph

Input:

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

Output:

$K$ shortest paths in $G$.

Complexity:

$O(k|V|^3)$ total time.

Comment:

Reference:

[Shier1979] (Bibtex)

P89: Generation of the $k$-th longest path in a tree

Input:

A tree $T = (V, E)$ and an integer $k$.

Output:

The $k$-th longest path in $T$.

Complexity:

$O(n\log^2 n)$ time.

Comment:

Reference:

[Megiddo1981] (Bibtex)

P178: Enumeration of all shortest paths in a graph

Input:

A graph $G$.

Output:

All shortest paths in $G$.

Complexity:

Comment:

Reference:

[Florian1981] (Bibtex)

P80: Enumeration of $k$ shortest paths of a directed graph

Input:

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

Output:

$k$ shortest paths that may contains cycles in $G$.

Complexity:

Comment:

Reference:

[Martins1984] (Bibtex)

P349: Enumeration of all quickest paths in a network

Input:

A network $N = (V, E, c, \ell)$.

Output:

All quickest paths in $N$.

Complexity:

$O(rS|V||E| + rS|V|^2\log|V|)$ total time.

Comment:

$c$ is a positive edge weight function and $\ell$ is a nonnegative edge weight function. $r$ is the number of distinct capacity value of $N$. $S$ is the number of solutions.

Reference:

[Rosen1991] (Bibtex)

P45: Counting all acyclic walks in a graph

Input:

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

Output:

The number of acyclic walks in $G$.

Complexity:

Comment:

Reference:

[Babic1993] (Bibtex)

P56: Enumeration of the $k$ shortest paths in a graph

Input:

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

Output:

The $k$ smallest shortest paths in $G$.

Complexity:

$O(k|E|)$ total time.

Comment:

Reference:

[Azevedo1993] (Bibtex)

P335: Enumeration of all constrained quickest paths in a network

Input:

A network $N = (V, E)$ and constraints $L$ and $C$.

Output:

All quickest paths in $N$.

Complexity:

$O(k|V|^2|E|)$ total time.

Comment:

$k$ is the number of solutions. A quickest path is a variant of a shortest path.

Reference:

[Gen-Huey1994] (Bibtex)

P58: Enumeration of the $k$ shortest paths in a directed graph

Input:

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

Output:

The $k$ smallest shortest paths in $G$.

Complexity:

$O(k|E|)$ total time

Comment:

Reference:

[Eppstein1998] (Bibtex)

P286: Enumeration of all minimal path conjunctions in a graph

Input:

A directed graph $G = (V, E)$, $s_1, s_2, t_1 \in V$, $T_2 \subseteq V$, and $\mathcal{P} = \{ (s_1, t_1)\} \cup \{(s_2, t): t\in T_2\}$.

Output:

All minimal path conjunctions in $G$.

Complexity:

Polynomial delay.

Comment:

A path conjunction is a edge subset $E' \subseteq E$ such that for all $(s, t) \in \mathcal{P}$, $s$ is connected to $t$ in the graph $G' = (V, E')$.

Reference:

[Boros2004a] (Bibtex)

P496: Enumeration of all minimal path-conjunctions of an undirected graph.

Input:

An undirected graph $G=(V, E)$ and $\mathcal{P} = \{(s_i, t_i ) \in V \times V \mid i \in [k] \}$.

Output:

All minimal path-conjunction of $G$.

Complexity:

Incremental polynomial time.

Comment:

A minimal path-conjunction is a minimal set of edges $E'$ such that any pair of vertices in $\mathcal{P}$ is connected in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)

P497: Enumeration of all minimal path-disjunctions of an undirected graph.

Input:

An undirected graph $G=(V, E)$ and $\mathcal{P} = \{(s_i, t_i ) \in V \times V \mid i \in [k] \}$.

Output:

All minimal path-disjunctions of $G$.

Complexity:

Incremental polynomial time.

Comment:

A minimal path-disjunction is a minimal set of edges $E'$ such that some pair of vertices in $\mathcal{P}$ is connected in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)

P498: Enumeration of all minimal path-conjunctions of a directed graph.

Input:

A directed graph $G = (V, E)$ and a family of pairs $\mathcal{P} = \binom{V_1}{2} \cup \dots \cup \binom{V_p}{2}$, where $V_1, \dots, V_p$ are disjoint vertex subset of $V$.

Output:

All minimal path-conjunctions of $G$ with respect to $\mathcal{P}$.

Complexity:

NP-hard.

Comment:

A minimal path-conjunction is a minimal set of edges $E'$ such that for all $i$, all vertices in $V_i$ belong to a connected component in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)

P499: Enumeration of all minimal path-conjunctions of a directed graph.

Input:

A directed graph $G = (V, E)$ and a family of pairs $\mathcal{P} = \{(s_1, t_1)\} \cup \{(s_2, t) \mid t \in T\}$, where $T \subseteq V$.

Output:

All minimal path-conjunctions of $G$.

Complexity:

Polynomial delay.

Comment:

A minimal path-conjunction is a minimal set of edges $E'$ such that any pair of vertices in $\mathcal{P}$ is connected in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)

P500: Enumeration of all minimal path-disjunctions of a directed graph.

Input:

A directed graph $G = (V, E)$ and a family of pairs $\mathcal{P} = \binom{V_1}{2} \cup \dots \cup \binom{V_p}{2}$, where $V_1, \dots, V_p$ are disjoint vertex subset of $V$.

Output:

All minimal path-disjunctions of $G$.

Complexity:

NP-hard.

Comment:

A minimal path-disjunctions is a minimal set of edges $E'$ such that for some $i$, all vertices in $V_i$ belong to a connected component in $(V, E')$.

Reference:

[Khachiyan2007] (Bibtex)

P10: Enumeration of all st-paths in a graph

Input:

A graph $G=(V,E)$ and $s, v \in V$.

Output:

All st-paths in $G$.

Complexity:

$O(|E| + \sum_{\pi \in \mathcal{P}_{st}(G)}|\pi|)$ total time.

Comment:

$\mathcal{P}_{st}(G)$ is the set of all st-paths in $G$.

Reference:

[Ferreira2012] (Bibtex)

P192: Enumeration of all $P_3$'s in a graph

Input:

A graph $G$.

Output:

All of all $P_3$'s in $G$.

Complexity:

$O(|E|^{1.5} + p_3(G))$ total time.

Comment:

$P_3$ is a induced path of $G$ with three vertices and $p_3(G)$ is the number of $P_3$ in $G$.

Reference:

[Hoang2013] (Bibtex)

P193: Enumeration of all $P_k$'s in a graph

Input:

A graph $G$ and an integer $k \ge 4$.

Output:

All of all $P_k$'s in $G$.

Complexity:

$O(|V|^{k-1} + p_k(G) + k\cdot c_k(G))$ total time.

Comment:

$P_k$ and $C_k$ are a induced path and cycle of $G$ with $k$ vertices, respectively. $p_k(G)$ and $c_k(G)$ are the number of $P_k$ and $C_k$ in $G$, respectively.

Reference:

[Hoang2013] (Bibtex)

P194: Enumeration of all $C_k$'s in a graph

Input:

A graph $G$ and an integer $k \ge 4$.

Output:

All of all $C_k$'s in $G$.

Complexity:

$O(|V|^{k-1} + p_k(G) + c_k(G))$ total time.

Comment:

$P_k$ and $C_k$ are a induced path and cycle of $G$ with $k$ vertices, respectively. $p_k(G)$ and $c_k(G)$ are the number of $P_k$ and $C_k$ in $G$, respectively.

Reference:

[Hoang2013] (Bibtex)

P13: Enumeration of all chordless $st$-paths in a graph

Input:

A graph $G=(V,E)$ and two vertices $s, t \in V$.

Output:

All chordless $st$-paths in $G$.

Complexity:

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

Comment:

$P$ is the number of chordless $st$-paths in $G$.

Reference:

[Ferreira2014] (Bibtex)

P14: Enumeration of all chordless st-paths in a graph

Input:

A graph $G=(V,E)$ and $s, t \in V$.

Output:

All chordless st-paths (from $s$ to $t$) in $G$.

Complexity:

$O(|V|+|E|)$ time per chordless st-path.

Comment:

Reference:

[Unoc] (Bibtex)