# Enumeration of Enumeration Algorithms and Its Complexity

This list is under construction. If you know some results not in the list or there is anything wrong, please let me know (e-mail: wasa[at]ist.hokudai.ac.jp).

Other useful catalogues for enumeration algorithms are provided by Komei Fukuda and Yasuko Matsui. There are some survey papers. (See survey section. )

Number of problems: 434, Number of reference: 300. Click each genre to open. without javascirpt version

Last update: 2015-11-03T23:46:57+0900 (JST) , XML data and Bibtex data

## Enumeration problems

### Geometry

#### Arrangement

P323: Enumeration of all cells in arrangements
Input: An arrangement of distinct hyperplanes.
Output: All cells in arrangements.
Complexity: $O(nm\ell(n,m)N)$ total time and $O(nm)$ space.
Comment: $n$ is the dimension, $m$ is the number of hyperplanes, and $\ell(n, m)$ is the time for solving an LP with $n$ variables and $m-1$ inequalities. $N$ is the number of solutions.
Reference: [Avis1996]

#### Face

P66: Enumeration of all arrangements
Input: An integer $n$ and $\mathcal{J} \subseteq \{+, -\}^n$.
Output: The set $\mathcal{F}$ of faces if $\mathcal{J}$ is the set of maximal faces of an oriented matroid
Complexity: $O(\max(n^2 |\mathcal{J}|^3, n^3 |\mathcal{J}|^2))$ total time.
Comment: Their paper treats a reconstruction of the location vectors of all faces from the graph.
Reference: [Fukuda1991]

#### Matching

P426: Enumeration of all non-crossing perfect matchings (and convex partitions) in a given points
Input: A point sets $P$ in a plane
Output: All non-crossing perfect matchings (and convex partitions) in $P$.
Complexity: After $O(2^nn^4)$ preprocessing time, polynomial delay.
Comment: $n$ is the number of points in $P$
Reference: [Wettstein2014]

#### Nearest neighbor

P46: Enumeration of the $k$ smallest distances between pairs of points
Input: $n$ points in a plane.
Output: The $k$ smallest distances between pairs of points in non-decreasing order.
Complexity: $O(n \log n + k \log k)$ total time and $O(n + k)$ space.
Comment: I'm looking for this paper.
Reference: [Dickerson1992]

#### Spanning tree

P49: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
Input: $n$ points in a plane
Output: The Euclidean $k$ best spanning trees of the given points.
Complexity: $O(k^2 n + n \log n)$ total time
Comment: An Euclidean spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the Euclidean distance between the corresponding vertices.
Reference: [Eppstein1992]
P50: Enumeration of the orthogonal $k$ best spanning trees in a plane with $n$ points
Input: $n$ points in a plane
Output: The orthogonal $k$ best spanning trees of the given points.
Complexity: $O(k^2 + k n \log \log (n/k) + n \log n)$ total time.
Comment: An orthogonal spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the $L_1$ distance between the corresponding vertices.
Reference: [Eppstein1992]
P328: Enumeration of all spanning trees of a plane
Input: A point set $P$.
Output: All spanning trees of $P$.
Complexity: $O(|P|^3N)$ total time and $O(|P|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Avis1996]
P60: Enumeration of the Euclidean $k$ best spanning trees in a plane with $n$ points
Input: $n$ points in a plane
Output: The Euclidean $k$ best spanning trees of the given points.
Complexity: $O(n \log n \log k + k \min(k, n)^{1/2})$ total time
Comment: An Euclidean spanning tree in a plane is a spanning tree of the complete graph whose vertices are all given points and the weight of an edge equal to the Euclidean distance between the corresponding vertices.
Reference: [Eppstein1997]

#### Triangulation

P81: Enumeration of all regular triangulations
Input: $n$ points.
Output: All regular triangulations of given points in $(d-1)$-dimensional space.
Complexity: $O(dsLP(r, ds)T)$ time and $O(ds)$ space.
Comment: $s$ is the upper bound of the number of simplcies contained in one regular triangulation, $LP(r, ds)$ denotes the time complexity of solving linear programming problem with $ds$ strict inequality constraints in $r$ variables, and $T$ is the number of regular triangulations.
P82: Enumeration of all spanning regular triangulations
Input: $n$ points.
Output: All spanning regular triangulations of given points in $(d-1)$-dimensional space.
Complexity: $O(dsLP(r, ds)T')$ time and $O(ds)$ space.
Comment: $s$ is the upper bound of the number of simplcies contained in one regular triangulation, $LP(r, ds)$ denotes the time complexity of solving linear programming problem with $ds$ strict inequality constraints in $r$ variables, and $T'$ is the number of regular triangulations.
P324: Enumeration of all triangulations of a point set
Input: A point set $P$.
Output: All triangulations of $P$.
Complexity: $O(|P|N)$ total time and $O(|P|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Avis1996]
P112: Enumeration of all triangulations in general dimensions
Input: Points.
Output: All triangulations.
Complexity: See the paper.
Comment: This algorithm uses the enumeration algorithm for maximal independent sets.
Reference: [Takeuchi]
P113: Enumeration of all regular triangulations in general dimensions
Input: Points.
Output: All regular triangulations.
Complexity: See the paper.
Comment: This algorithm uses the enumeration algorithm for maximal independent sets.
Reference: [Takeuchi]
P298: Enumeration of all triangulation paths of a point set
Input: A point set $P$.
Output: All triangulation paths of $P$.
Complexity: $O(N|P|^3\log |P|)$ time and $O(|P|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Dumitrescu2001]
P279: Enumeration of all pseudotriangulations of a finite point set
Input: A point set $S$ of size $n$.
Output: All pointed pseudotriangulations of $S$.
Complexity: $O(\log n)$ time per solution with linear space.
Comment:
Reference: [Bereg2005]
P265: Enumeration of all pseudotriangulations of a point set
Input: A point set $P$.
Output: All pseudotriangulations of $P$.
Complexity: $O(n)$ time per pseudotriangulation.
Comment: $n$ is the number of points in $P$.
Reference: [Bronnimann2006a]
P171: Enumeration of all triangulations of a convex polygon of $n$ vertices with numbered
Input: A convex polygon $P$ with $n$ vertices that are numbered.
Output: All triangulations of $P$.
Complexity: $O(1)$ time per triangulation and $O(n)$ space.
Comment:
Reference: [Parvez2009]
P172: Enumeration of all triangulations of a convex polygon of $n$ vertices
Input: A convex polygon $P$ with $n$ vertices that are not numbered.
Output: All triangulations of $P$.
Complexity: $O(n^2)$ time per triangulation and $O(n)$ space.
Comment:
Reference: [Parvez2009]

### Graph

#### $k$-degenerate graph

P30: Enumerate well-ordered (strongly) $k$-generate with $n$ vertices
Input: $n$: the number of vertices.
Output: All well-ordered (strongly) $k$-degenerate graphs with $n$ vertices.
Complexity: $O(nm+m^2)$ time per enumerated and printed graph.
Comment: $m$ is the number of edges of printed graphs.
Reference: [Bauer2010a]
P31: Enumerate well-ordered (strongly) $k$-generate with $n$ vertices and $m$ edges
Input: $n$: the number of vertices, $m$: the number of edges.
Output: All well-ordered (strongly) $k$-degenerate graphs with $n$ vertices and $m$ edges.
Complexity: $O(n^{3/2}m^2)$ time per enumerated and printed graph.
Comment:
Reference: [Bauer2010a]

#### Bounded union

P268: Enumeration of all bounded union
Input: A graph with $h$ multiedges each with at most $d$ vertices.
Output: All minimal subset $U$ of at most $k$ vertices that entirely includes at least one set from each multiedge.
Complexity: $O(dc^{k+1}h + \min(kc^{2k}, hkc^k))$ time.
Comment:
Reference: [Damaschke2006]

#### Bridge

P136: Enumeration of all bridge-avoiding extensions of a graph
Input: A graph $G = (V, E)$ and an edge subset $B \subseteq E$.
Output: All bridge-avoiding extensions of $G$.
Complexity: $O(K^2 \log(K) |E|^2 + K^2(|V|+|E|)|E|^2)$ total time.
Comment: $K$ is the number of bridge-avoiding extensions. $X$ is a bridge-avoiding extensions of $G$ if $X$ is a minimal edge set $X \subseteq E \setminus B$ such that no edge $b \in B$ is a bridge in $(V, B\cup X)$.
Reference: [Khachiyan2008a]

#### Bubble

P9: Enumeration of all bubbles in a directed graph
Input: A directed graph $G=(V, E)$ and a source $s$.
Output: All bubbles with a given source $s$.
Complexity: $O(|V| + |E|)$ delay with $O(|V|(|V| + |E|))$ preprocessing time.
Comment: An $(s,t)$-bubble is two disjoint $(s,t)$-paths that only share $s$ and $t$.
Reference: [Birmele2012]
P191: Enumeration of all $(s, t, \alpha_1, \alpha_2)$-bubble in a directed graph
Input: A directed graph $G = (V, E)$, source vertex $s$, and two upper bounds $\alpha_1$ and $\alpha_2$.
Output: All $(s, t, \alpha_1, \alpha_2)$-bubble in $G$.
Complexity: $O(|V|(|E|+|V|\log |V|))$ delay.
Comment: A pair of two vertex-disjoint $(s, t)$-paths $p_1$ and $p_2$ is $(s, t, \alpha_1, \alpha_2)$-bubble in $G$, if $|p_1| \le \alpha_1$ and $|p_2| \le \alpha_2$.
Reference: [Sacomoto2013b]

#### Chord diagram

P296: Enumeration of all non-isomorphic chord diagrams
Input: An integer $2n$.
Output: All non-isomorphic chord diagrams with $2n$ points.
Complexity:
Comment: A \textit{chord diagram} is a set of $2n$ points on an oriented circle (counterclockwise) joined pairwise by $n$ chords. In an experiment, their algorithm runs in almost CAT, but there is no Mathematical proof.

#### Chordal graph

P270: Enumeration of all chordal graphs in a graph
Input: A graph $G$.
Output: All chordal graphs in $G$.
Complexity: $O(1)$ delay with $O(n^3)$ space.
Comment: Using reverse search.
Reference: [Kiyomi2006]
P272: Enumeration of all chordal supergraph that contains a given graph
Input: A graph $G = (V, E)$.
Output: All chordal supergraphs each of which contain $G$.
Complexity: $O(|V|^3)$ time for each and $O(|V|^2)$ space.
Comment:
Reference: [Kiyomi2006a]
P213: Enumeration of all chordal sandwiches in a graph
Input: A graph $G = (V, E)$.
Output: All chordal sandwiches in $G$.
Complexity: Polynomial delay with polynomial space.
Comment: I'm looking for this paper.
Reference: [Kijima2010]

#### Clique

P410: Enumeration of all cliques in a graph
Input: A graph $G$.
Output: All cliques in $G$.
Complexity:
Comment: They pointed out Augustson and Minker's algorithm has two errors.
Reference: [Mulligan1972]
P33: Enumeration of all maximal clique in a graph
Input: An undirected graph $G=(V, E)$.
Output: All maximal clique.
Complexity:
Comment:
Reference: [Akkoyunlu1973]
P188: Enumeration of all cliques in a graph
Input: A graph $G$.
Output: All cliques in $G$.
Complexity:
Comment:
Reference: [Bron1973]
P404: Enumeration of all cliques in an undirected graph
Input: An undirected graph $G$.
Output: All cliques in $G$.
Complexity:
Comment:
Reference: [Johnston1976]
P387: Enumeration of all maximal cliques in a given graph
Input: A graph $G$.
Output: All maximal cliques in $G$.
Complexity:
Comment:
Reference: [Gerhards1979]
P107: Enumeration of all maximum cliques in a circle graph
Input: A circle graph $G = (V, E)$.
Output: All maximum cliques in $G$.
Complexity: $O(1)$ time per maximum clique.
Comment: A graph is a circle graph if it is the intersection graph of chords in a circle. The definition of a circle graph can be found in Information System on Graph Classes and their Inclusions. I'm looking for this paper.
Reference: [Rotem1981]
P184: Enumeration of all cliques in a connected graph
Input: A connected graph $G = (V, E)$ and an order $l \ge 2$ of cliques.
Output: All cliques in $G$.
Complexity: $O(l\alpha(G)^{l-2}|E|)$ total time and linear space.
Comment: $\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed. I'm looking for this paper.
Reference: [Chiba1985]
P185: Enumeration of all maximal cliques in a connected graph
Input: A connected graph $G = (V, E)$.
Output: All maximal cliques in $G$.
Complexity: $O(\alpha(G)|E|)$ total time and linear space.
Comment: $\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed. I'm looking for this paper.
Reference: [Chiba1985]
P77: Enumeration of all maximum cliques of a circular-arc graph
Input: A circular-arc graph $G =(V, E)$.
Output: All maximum cliques of $G$.
Complexity: $O(|V|^{3.5} + N)$.
Comment: $N$ is the number of maximum cliques of $G$. For a family $A$ of arcs on a circle, a graph $G = (V, E)$ is called the \textit{circular-arc graph} for $A$ if there exists a one-to-one correspondence between $V$ and $A$ such that two vertices in $V$ are adjacent if and only if their corresponding arcs in $A$ intersect.
Reference: [Kashiwabara1992]
P20: Enumeration of all maximal cliques in a graph
Input: A graph $G=(V,E)$.
Output: All maximal cliques included in $G$.
Complexity: $O(M(n))$ time delay and $O(n^2)$ space, or $O(\delta^4)$ time delay and $O(n+m)$ space, after $O(nm)$ preprocessing.
Comment: $M(n)$: the time needed to multiply two $n \times n$ matrices, $\delta$: maximum degree of $G=(V,E)$, $n$: total number of vertices, and $m$: total number of edges.
Reference: [Makino2004]
P21: Enumeration of all maximal cliques in a bipartite graph
Input: A bipartite graph $G=(V,E)$.
Output: All maximal bicliques included in $G$.
Complexity: $O(M(n))$ time delay and $O(n^2)$ space, or $O(\delta^4)$ time delay and $O(n+m)$ space, after $O(nm)$ preprocessing.
Comment: $M(n)$: the time needed to multiply two $n \times n$ matrices, $\delta$: maximum degree of $G=(V,E)$, $n$: total number of vertices, and $m$: total number of edges.
Reference: [Makino2004]
P180: Enumeration of all maximal cliques in a dynamic graph
Input: A graph $G_t = (V, E_t)$.
Output: All maximal cliques in $G_t$.
Complexity:
Comment:
Reference: [Stix2004]
P289: Enumeration of all maximal cliques in a dynamic graph
Input: A dynamic graph $G$.
Output: All maximal cliques in $G$.
Complexity:
Comment:
Reference: [Stix2004]
P280: Enumeration of all bicliques in a graph in lexicographical order
Input: A graph $G = (V, E)$.
Output: All bicliques in $G$.
Complexity: $O(|V|^3)$ delay and $O(2^{|V|})$ space.
Comment: There is no polynomial-delay enumeration algorithm for all bicliques in reverse lexicographical order unless $P = NP$.
Reference: [Dias2005]
P281: Enumeration of all $c$-isolated cliques in a graph
Input: A graph $G = (V, E)$ and a positive integer $c$.
Output: Enumeration of all $c$-isolated cliques in $G$.
Complexity: $O(c^52^{2c}|E|)$ total time.
Comment: A clique $S$ is said to be $c$-isolated if $|E(S,G − S)| < ck$, where $k$ is the number of vertices in $S$ and $E(G_A, G_B)$ denotes the set of edges connecting the two subgraphs $G_A$ and $G_B$ directly, i.e., the set of edges $(v_1,v_2)$ such that $v_1$ is in $G_A$ and $v_2$ in $G_B$.
Reference: [Ito2005]
P222: Enumeration of all maximal cliques in a graph
Input: A graph $G = (V, E )$.
Output: All maximal Cliques in $G$.
Complexity: $O(\frac{\Delta M_c Tri^2}{P})$ delay and $O(|V| + |E|)$ space.
Comment: $\Delta$ is the maximum degree in $G$, $M_c$ is the size of the maximum clique in $G$, and $Tri$ is the number of triangles in $G$. This algorithm runs on the computer with $P$ processors.
Reference: [Du2009]
P271: Enumeration of all cliques in a chordal graph
Input: A chordal graph $G$.
Output: All cliques in $G$.
Complexity: $O(1)$ time per solution on average.
Comment:
Reference: [Kiyomi2006]
P278: Enumeration of all maximal cliques in a graph
Input: A graph $G = (V, E)$.
Output: All maximal cliques in $G$.
Complexity: $O(3^{n/3})$ total time.
Comment:
Reference: [Tomita2006]
P260: Enumeration of $K$-largest maximal cliques in a graph
Input: A graph $G$.
Output: $K$-largest maximal cliques in $G$.
Complexity:
Comment:
Reference: [Bulo2007]
P247: Enumeration of all maximal cliques in a graph
Input: A graph $G$.
Output: All maximal cliques in $G$.
Complexity:
Comment:
Reference: [Pan2008]
P224: Enumeration of all maximal bicliques in a bipartite graph
Input: A bipartite graph $G = (U, V, E)$.
Output: All maximal bicliques in $G$ in lexicographical order on $U$.
Complexity: $O((|U| + |V|)^2)$ delay with exponential space.
Comment:
Reference: [Gely2009]
P225: Enumeration of all maximal cliques in a comparability graph
Input: A comparability graph $G = (V, E)$.
Output: All maximal cliques in $G$ in lexicographical order.
Complexity: $O(|V|)$ delay and $O(|V| + |E|)$ space.
Comment:
Reference: [Gely2009]
P226: Enumeration of all maximal cliques in a graph
Input: A graph $G = (V, E)$.
Output: All maximal cliques in $G$ in lexicographical order.
Complexity: $O(|V||E|)$ delay with exponential space.
Comment:
Reference: [Gely2009]
P227: Enumeration of all maximal cliques in a graph
Input: A graph $G$.
Output: All maximal cliques in $G$.
Complexity:
Comment: This algorithm can be paralleled.
Reference: [Schmidt2009]
P229: Enumeration of all $c$-isolated maximal clique in a graph
Input: A graph $G = (V, E)$ and a positive real number $c$.
Output: All $c$-isolated maximal clique in $G$.
Complexity: $O(c^42^{2c}|E|)$ total time.
Comment:
Reference: [Ito2009]
P230: Enumeration of all $c$-isolated pseudo-clique in a graph
Input: A graph $G = (V, E)$ and a positive real number $c$.
Output: All $c$-isolated $PC(k-\log k, \frac{k}{\log k})$ in $G$.
Complexity: $O(c^42^{2c}|E|)$ total time.
Comment: $PC(\alpha, \beta)$ is a induced subgraph of $G$ with an average degree at least $\alpha$ and the minimum degree at least $\beta$.
Reference: [Ito2009]
P232: Enumeration of all avg-$c$-isolated maximal cliques in a graph
Input: A graph $G = (V, E)$ and an integer $c$.
Output: All avg-$c$-isolated maximal cliques in $G$.
Complexity: $O(2^cc^5|E|)$ total time.
Comment: A vertex set $S \subseteq V$ with $k$ vertices is ave-$c$-isolated if it has less than $ck$ outgoing edges, where an outgoing edge is an edge between a vertex in $S$ and a vertex in $V \setminus S$.
Reference: [Huffner2009]
P233: Enumeration of all max-$c$-isolated maximal cliques in a graph
Input: A graph $G = (V, E)$ and an integer $c$.
Output: All max-$c$-isolated maximal cliques in $G$.
Complexity: $O(2^cc^5|E|)$ total time.
Comment: A vertex set $S \subseteq V$ with $k$ vertices is max-$c$-isolated if every vertex in $S$ has less than $c$ neighbors in $V \setminus S$.
Reference: [Huffner2009]
P210: Enumeration of all cliques in a graph with degeneracy $d$
Input: A graph $G = (V, E)$ with degeneracy $d$.
Output: All cliques in $G$.
Complexity: $O(d|V|3^{d/3})$ time.
Comment: They also show the largest possible number of maximal cliques in $G$. The number is $(|V|-d)3^{d/3}$.
Reference: [Eppstein2010]
P254: Enumeration of all pseudo-cliques in a graph
Input: A graph $G = (V, E)$ and a threshold $\theta$.
Output: All pseudo-cliques in $G$, whose densities are no less than $\theta$.
Complexity: $O(\Delta |V| + \mathrm{min}\{\Delta^2, |V| + |E|\})$ delay with $O(|V| + |E|)$ space.
Comment: $\Delta$ is the maximum degree of $G$. The density of a subgraph $G[S]$ induced by $S \subseteq V$ is given by the number of edges over the number of all its vertex pairs.
Reference: [Uno2008a]
P201: Enumeration of all maximal cliques in a graph with limited memory
Input: A graph $G$.
Output: All maximal graphs in $G$.
Complexity: See the paper.
Comment:
Reference: [Cheng2012b]
P34: Enumeration of all maximal cliques in a graph
Input: An undirected graph $G=(V, E)$.
Output: All maximal clique.
Complexity: $O(\delta\cdot H^3)$ time delay and $O(n+m)$ space.
Comment: $H$ satisfies $|\{v\in V | \sigma(v)\ge H\}| \le H$.
Reference: [Chang2013]
P190: Enumeration of all maximal cliques in a graph
Input: A graph $G$.
Output: All maximal cliques in $G$.
Complexity:
Comment:
Reference: [Henry2013]

#### Coloring

P122: Enumeration of all the edge colorings in a bipartite graph
Input: A bipartite graph $G = (V, E)$.
Output: All edge colorings in $G$.
Complexity: $O(\Delta|E|)$ time per solution and space.
Comment: $\Delta$ is the maximum degree in $G$. I'm looking for this paper.
Reference: [Yasuko1994]
P86: Enumeration of all the edge colorings of a bipartite graph
Input: A bipartite graph $B = (V, E)$.
Output: All the edge colorings pf $B$.
Complexity: $O(T(|V|+|E|+\Delta) + K \min \{|V|^2 + |E|, T(|V|, |E|, \Delta)\})$ total time and $O(|E|\Delta)$ space.
Comment: $\Delta$ is the number of maximum degree and $T(|V|, |E|, \Delta)$ is the time complexity of an edge coloring algorithm.
Reference: [Matsui1996b]
P87: Enumeration of all the edge colorings of a bipartite graph
Input: A bipartite graph $B = (V, E)$.
Output: All the edge colorings pf $B$.
Complexity: $O(|V|)$ time per solution and $O(|E|)$ space.
Comment: I'm looking for this paper.
Reference: [Matsui1996a]

#### Connected

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]
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]

#### Cut

P399: Enumeration of all cuts between all pair of vertices in a given graph
Input: A graph $G$.
Output: All cuts bewteen all pair of vertices in $G$
Complexity:
Comment:
Reference: [Martelli1976a]
P114: Enumeration of all cutsets in a graph
Input: A graph $G = (V, E)$.
Output: All cutsets in $G$.
Complexity: $O((|V| + |E|)(\mu + 1))$ total time and $O(|V| + |E|)$ or $O(|V|^2)$ space.
Comment: $\mu$ is the number of solutions.
Reference: [Tsukiyama1980]
P70: Enumeration of $k$ best cuts in a directed graph
Input: A directed graph $G = (V, E)$.
Output: $k$ best cuts in $G$.
Complexity: $O(k|V|^4)$ total time.
Comment:
Reference: [Hamacher1984a]
P372: Enumeration of $K$-best cuts in a network
Input: A graph $G = (V, E)$.
Output: $K$-best cuts in $G$.
Complexity: $O(K\cdot |V|^4)$ time.
Comment:
Reference: [Hamacher1984a]
P365: Enumeration of all articulation pairs in a planar graph
Input: An undirected graph $G = (V, E)$.
Output: All articulation pairs in $G$.
Complexity: $O(|V|^2)$ total time.
Comment:
Reference: [Laumond1985]
P71: Enumeration of all minimum-size separating vertex sets in a graph
Input: A graph $G = (V, E)$.
Output: All minimum-size separating vertex sets.
Complexity: $\Theta(M|V| + C) = O(2^kn^3)$ total time.
Comment: $M$ is the number of solutions, $k$ is the connectivity of $G$, and $C = k|V| \min(k(|V|+|E|), A)$, where $A$ is the time complexity of the best maximum network flow algorithm for unit network. I'm looking for this paper.
Reference: [Kanevsky1993]
P181: Enumeration of all minimal separators in a graph
Input: A graph $G = (V, E)$.
Output: All minimal separators in $G$.
Complexity: $O(|V|^6R)$ total time.
Comment: $R$ is the number of solutions.
Reference: [Kloks1994]
P91: Enumeration of all $(s, t)$-cuts in a graph
Input: A graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output: All $(s, t)$-cuts in $G$.
Complexity: $O(|E|)$ time per cut.
Comment:
Reference: [Provan1996]
P92: Enumeration of all $(s, t)$-cuts in a directed graph
Input: A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output: All $(s, t)$-cuts in $G$.
Complexity: $O(|E|)$ time per cut.
Comment:
Reference: [Provan1996]
P93: Enumeration of all $(s, t)$-uniformly directed cuts in a directed graph
Input: A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output: All $(s, t)$-uniformly directed cuts in $G$.
Complexity: $O(|V|)$ time per cut.
Comment: An \textit{undirected directed cut} is also called a UDC. An $(s, t)$-DUC is an $(s, t)$-cut $(X, Y)$ such that $(X, Y) = \emptyset$, where $(X, Y) = \{(u, v) \in E: u\in X, v\in Y\}$.
Reference: [Provan1996]
P94: Enumeration of all minimum weighted $(s, t)$ cuts in an weighted graph
Input: An weighted graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output: All minimum weighted $(s, t)$ cuts in $G$.
Complexity: $O(|V|)$ time per cut.
Comment:
Reference: [Provan1996]
P95: Enumeration of all semidirected $(s, t)$ cuts in a directed graph
Input: A directed graph $G = (V, E)$ and two vertices $s, t$ in $G$.
Output: All semidirected $(s, t)$ cuts in $G$.
Complexity: $O(|V||E|)$ time per cut.
Comment: For a subset $D$ of directed edges, a \textit{semidirected $(s, t)$ cut} with respect to $D$ is an $(s, t)$ cut $(X, Y)$ such that $(X, Y) \cup (Y, X)$ defnes an undirected $(s, t)$ cutset and such that $(X, Y) \cap D = \emptyset$, where a \textit{cutset} is an minimal cut set.
Reference: [Provan1996]
P96: Enumeration of all strong $(s, K)$ cutsets in a graph
Input: A graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output: All strong $(s, K)$ cutsets in $G$.
Complexity: $O(|E|)$ time per cut.
Comment: An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{strong $(s, K)$ cutset} is minimal cuts of the form $(X, Y)$ where $s \in X$ and $K \subseteq Y$.
Reference: [Provan1996]
P97: Enumeration of all strong $(s, K)$ cutsets in a directed graph
Input: A directed graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output: All strong $(s, K)$ cutsets in $G$.
Complexity: $O(|E|)$ time per cut.
Comment: An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{strong $(s, K)$ cutset} is minimal cuts of the form $(X, Y)$ where $s \in X$ and $K \subseteq Y$.
Reference: [Provan1996]
P98: Enumeration of all quasi $(s, K)$ cuts in a graph
Input: A graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output: All quasi $(s, K)$ cutsets in $G$.
Complexity: $O(|E|)$ time per cut.
Comment: An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{Quasi $(s, K)$ cut} is an edge set that is strong $(s, A)$-cutsets for some $A \subseteq K$ and $A \neq \emptyset$.
Reference: [Provan1996]
P99: Enumeration of all quasi $(s, K)$ cuts in a directed graph
Input: A directed graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output: All quasi $(s, K)$ cutsets in $G$.
Complexity: $O(|E|)$ time per cut.
Comment: An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{Quasi $(s, K)$ cut} is an edge set that is strong $(s, A)$-cutsets for some $A \subseteq K$ and $A \neq \emptyset$.
Reference: [Provan1996]
P100: Enumeration of all $(s, K)$ cutsets in a graph
Input: A graph $G = (V, E)$ , $s\in V$ and $K \subseteq V \setminus \{s\}$.
Output: All $(s, K)$ cutsets in $G$.
Complexity: $O(|E|)$ time per cut.
Comment: An \textit{$(s, K)$-cut} is defined to be any cut $(X, Y)$ for which $s \in X$ and $K \cap Y \neq \emptyset$. A \textit{$(s, K)$ cutset} is minimal $(s, K)$ cuts.
Reference: [Provan1996]
P72: Enumeration of all minimal $a$-$b$ separators in a graph
Input: An undirected connected simple graph $G = (V, E)$, non-adjacent vertices $a$ and $b$ in $G$.
Output: All minimal $a$-$b$ separator of $G$.
Complexity: $O(R_{ab}|V|^3)$ total time.
Comment: $R_{ab}$ is the number of minimal $a$-$b$ separators.
Reference: [Shen1997]
P320: Enumeration of all minimal $a$-$b$ separators in a graph
Input: An undirected connected simple graph $G = (V, E)$, non-adjacent vertices $a$ and $b$ in $G$.
Output: All minimal $a$-$b$ separator of $G$.
Complexity: $O(R_{ab}|V|/\log|V|)$ total time.
Comment: $R_{ab}$ is the number of minimal $a$-$b$ separators. This algorithm needs $O(|V|^3)$ processors on a CREW PRAM.
Reference: [Shen1997]
P316: Enumeration of all minimal separators of a graph
Input: A graph $G = (V, E)$.
Output: All minimal separators of $G$.
Complexity: $O(|V|^5R)$ total time.
Comment: $R$ is the number of solutions.
Reference: [Kloks1998]
P302: Enumeration of all minimal separator of a graph
Input: A graph $G = (V, E)$.
Output: All minimal separator of $G$.
Complexity: $O(|V|^3)$ time per solution.
Comment:
Reference: [Berry2000]
P297: Enumeration of all minimal separator of a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All minimal separator of $G$.
Complexity: $O(|V|+|E|)$ total time.
Comment:
Reference: [Chandran2001]
P282: Enumeration of all cut conjunctions for a given set of vertex pairs in a graph
Input: A graph $G = (V,E)$, and a collection $B = \{(s_1,t_1),...,(s_k,t_k)\}$ of $k$ vertex pairs $s_i,t_i \in V$.
Output: All cut conjunctions for $B$ in $G$.
Complexity: Incremental polynomial time.
Comment: A minimal edge sets $X \subseteq E$ is a \textit{cut conjunction} if, for all $i = 1, \dots, k$, vertices $s_i$ and $t_i$ is disconnected in $G' = (V, E\setminus X)$. A cut conjunction is a generalization of an $s-t$ cut.
Reference: [Khachiyan2005]
P275: Enumeration of all minimal separators of a 3-connected planar graph
Input: A 3-connected planar graph $G = (V, E)$.
Output: All minimal separators of $G$.
Complexity: $O(|V|)$ time per solution.
Comment:
Reference: [Mazoit2006]
P135: Enumeration of all cut conjunctions of a graph
Input: A graph $G = (V, E)$ and a collection $B = \{(s_1, t_1), \dots, (s_k, t_k)\}$.
Output: All cut conjunctions of $G$.
Complexity: $O(K^2 \log(K) |V||E|^2 + K^2|B|(|V|+|E|)|E|^2)$ total time.
Comment: $K$ is the number of cut conjunctions. $X$ is a cut conjunctions of $G$ if $X$ is a minimal edge set such that for all $i = 1, \dots, k$, a pair of vertices $s_i$ and $t_i$ is disconnected in $(V, E\setminus X)$.
Reference: [Khachiyan2008a]
P186: Enumeration of all $(s, t)$-cuts in an weighted directed graph
Input: An weighted directed graph $G = (V, E)$.
Output: All cuts in $G$ by non-decreasing weights ordering.
Complexity: $O(|V||E|\log(|V|^2/|E|))$ delay.
Comment:
Reference: [Yeh2010]
P187: Enumeration of all $(s, t)$-cuts in an weighted undirected graph
Input: An weighted undirected graph $G = (V, E)$.
Output: All cuts in $G$ by non-decreasing weights ordering.
Complexity: $O(|V||E|\log(|V|^2/|E|))$ delay.
Comment:
Reference: [Yeh2010]

#### Cycle

P428: 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]
P429: Enumeration of all cycles in a graph
Input: A graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Welch1965]
P393: Enumeration of all simple cycles in a graph
Input: A graph $G$.
Output: All simple cycles in $G$.
Complexity:
Comment:
Reference: [Ponstein1966]
P422: Enumeration of all circuits in a graph
Input: A graph $G$.
Output: All circuits in $G$.
Complexity:
Comment:
Reference: [Welch1966]
P418: Enumeration of all Hamiltonian circuits in a graph
Input: A graph $G$.
Output: All Hamiltonian circuits in $G$.
Complexity:
Comment:
Reference: [Yau1967]
P420: Enumeration of all directed circuits in a directed graph
Input: A directed graph $G$.
Output: All directed circuits in $G$.
Complexity:
Comment:
Reference: [Kamae1967]
P415: Enumeration of all cycles in a graph
Input: A graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Danielson1968]
P414: Enumeration of all cycles in a graph
Input: A graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Rao1969]
P391: Enumeration of all elementary circuit in a graph
Input: A graph $G$.
Output: All elementary circuit in $G$.
Complexity:
Comment:
Reference: [Tiernan1970]
P430: Enumeration of all cycles in a graph
Input: A graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Char1970]
P407: Enumeration of all cycles in an undirected graph
Input: An undirected graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Weinblatt1972]
P413: 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]
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]
P431: 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]
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]
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:
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:
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]
P318: 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]
P243: Enumeration of all cycles in a graph
Input: A graph $G$.
Output: All cycles in $G$.
Complexity:
Comment:
Reference: [Wild2008]
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]
P245: Enumeration of all chordless cycles in a graph
Input: A graph $G$.
Output: All chordless cycles in $G$.
Complexity:
Comment:
Reference: [Wild2008]
P246: Enumeration of all Hamiltonian cycles in a graph
Input: A graph $G$.
Output: All Hamiltonian cycles in $G$.
Complexity:
Comment:
Reference: [Wild2008]
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]
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]
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]

#### Dominating set

P240: Enumeration of all minimal dominating sets in a graph
Input: A graph $G = (V, E)$.
Output: All minimal dominating sets in $G$.
Complexity: $O(1.7159^{|V|})$ total time.
Comment:
Reference: [Fomin2008]
P228: Enumeration of $z$ smallest weighted edge dominating sets in a graph
Input: An weighted graph $G = (V, E)$, and positive integers $k$ and $z$. Each edge of $G$ has a positive weight.
Output: $z$ smallest weighted edge dominating sets in $G$.
Complexity: $O(5.6^{2k}k^4z^2 +4^{2k}k^3z|V|)$ total time.
Comment:
Reference: [Wang2009]
P202: Enumeration of all minimal dominating sets in a line graph
Input: A line graph $G$.
Output: All minimal dominating sets in $G$.
Complexity: $O(||G||^5N^6)$ total time.
Comment: $||G||$ is the size of $G$ and $N$ is the number of minimal dominating sets in $G$.
Reference: [Kante2012]
P203: Enumeration of all minimal dominating sets in a path graph or $(C_4, C_5, craw)$-free graph
Input: A line graph or $(C_4, C_5, craw)$-free graph $G$.
Output: All minimal dominating sets in $G$.
Complexity: $O(||G||^2N^3)$ total time.
Comment: $||G||$ is the size of $G$ and $N$ is the number of minimal dominating sets in $G$.
Reference: [Kante2012]
P204: Enumeration of all minimal edge-dominating sets in a graph
Input: A graph $G$.
Output: All minimal edge-dominating sets in $G$.
Complexity: $O(||L(G)||^5N^6)$ total time.
Comment: $L(G)$ is the line graph of $G$, $||L(G)||$ is the size of $L(G)$, and $N$ is the number of minimal edge-dominating sets in $G$.
Reference: [Kante2012]
P35: Enumeration of all minimal dominating sets in an undirected permutation graph
Input: An undirected permutation graph $G=(V, E)$.
Output: All minimal dominating sets.
Complexity: $O(|V|)$ delay with $O(|V|^8)$ pre-processing.
Comment:
Reference: [Kante2013]
P36: Enumeration of all minimal dominating sets in an undirected interval graph
Input: An undirected interval graph $G=(V, E)$.
Output: All minimal dominating sets.
Complexity: $O(|V|)$ delay with $O(|V|^3)$ pre-processing.
Comment:
Reference: [Kante2013]
P124: Enumeration of all minimal edge dominating sets in a graph
Input: A graph $G = (V, E)$.
Output: All minimal edge dominating sets in $G$.
Complexity: $O(|V|^6|\mathcal{L}|)$ delay.
Comment: $\mathcal{L}$ is the set of already generated solutions.
Reference: [Golovach2013a]
P125: Enumeration of all minimal dominating sets in a line graph
Input: A line graph $G = (V, E)$.
Output: All minimal dominating sets in $G$.
Complexity: $O(|V|^2|E|^2|\mathcal{L}|)$ delay.
Comment: $\mathcal{L}$ is the set of already generated solutions.
Reference: [Golovach2013a]
P126: Enumeration of all minimal edge dominating sets in a bipartite graph
Input: A bipartite graph $G = (V, E)$.
Output: All minimal edge dominating sets in $G$.
Complexity: $O(|V|^4|\mathcal{L}|)$ delay.
Comment: $\mathcal{L}$ is the set of already generated solutions.
Reference: [Golovach2013a]
P127: Enumeration of all minimal dominating sets in the line graph of a bipartite graph
Input: A graph $G = (V, E)$.
Output: All minimal dominating sets in $G$.
Complexity: $O(|V|^2|E||\mathcal{L}|)$ delay.
Comment: $\mathcal{L}$ is the set of already generated solutions.
Reference: [Golovach2013a]
P128: Enumeration of all minimal dominating sets in a graph of girth at least 7
Input: A graph $G = (V, E)$ of girth at least 7.
Output: All minimal dominating sets in $G$.
Complexity: $O(|V|^2|E||\mathcal{L}|^2)$ delay.
Comment: $\mathcal{L}$ is the set of already generated solutions.
Reference: [Golovach2013a]
P189: Enumeration of all 2-dominating sets in a tree
Input: A tree $T = (V, E)$.
Output: All 2-dominating sets of $T$.
Complexity: $O(1.3248^n)$ total time.
Comment: If a subset $U\subseteq V$ is a 2-dominating set if every vertex $v \in V \setminus U$ has at least two neighbors in $U$.
Reference: [Krzywkowski2013]
P348: Enumeration of all minimal dominating sets in a $P_6$-free chordal graph
Input: A $P_6$-free chordal graph $G = (V, E)$.
Output: All minimal dominating sets in $G$.
Complexity: Linear delay with $O(|V|^2)$ space.
Comment:
Reference: [Kante2014]
P425: Enumeration of all minimal dominating sets in a chordal bipartite graph
Input: A chordal bipartite graph $G$.
Output: All minimal dominating sets in $G$.
Complexity: $O(n^3m|\mscrL|^2)$ delay and the total running time is $O(n^3m|\mscrL^*|^2)$.
Comment: $n$ is the number vertices in $G$, $m$ is the number of edges in $G$, $\mscrL$ is the family of already generated minimal dominating sets, and $\mscrL^*$ is the family of all minimal dominating sets.
Reference: [Golovach2015]

#### Drawing

P167: Enumeration of all rectangle drawings with $n$ faces
Input: An integer $n$.
Output: All rectangle drawings with $n$ faces.
Complexity: $O(n)$ time per drawing and space.
Comment: I'm looking for this paper.
Reference: [Takagi2004]

#### Feedback arc set

P434: Enumeration of all minimal feedback arc sets in a graph
Input: A graph $G$.
Output: All minimal feedback arc sets in $G$.
Complexity:
Comment:
Reference: [Yau1967]
P24: Enumeration of all minimal feedback arc sets in a directed graph
Input: A directed graph $G=(V,E)$.
Output: All minimal feedback arc sets in $G$.
Complexity: $O(|V||E|(|V|+|E|))$ time delay.
Comment:
Reference: [Schwikowski2002]

#### Feedback vertex set

P433: Enumeration of all minimal feedback vertex sets in a graph
Input: A graph $G$.
Output: All minimal feedback vertex sets in $G$.
Complexity:
Comment:
Reference: [Yau1967]
P177: Enumeration of all feedback vertex sets in a strongly connected directed graph
Input: A strongly connected directed graph $G = (V, E)$ and an integer $k$.
Output: All feedback vertex sets of size $k$ in $G$.
Complexity: $O(|V|^{k-1}|E|)$ total time and $O(|E|)$ space.
Comment:
Reference: [Garey1978]
P22: Enumeration of all minimal feedback vertex sets in a graph
Input: A graph $G=(V,E)$.
Output: All minimal feedback vertex sets in $G$.
Complexity: $O(|V||E|(|V|+|E|))$ time delay.
Comment:
Reference: [Schwikowski2002]
P23: Enumeration of all minimal feedback vertex sets in a directed graph
Input: A directed graph $G=(V,E)$.
Output: All minimal feedback vertex sets in $G$.
Complexity: $O(|V|^2(|V|+|E|))$ time delay.
Comment:
Reference: [Schwikowski2002]

#### General

P341: Enumeration of all graphs in an almost sure first order fimiles
Input: A first order language $\theta$.
Output: All graphs in $\mathcal{G}_\theta$.
Complexity: Polynomial space and delay.
Comment:
Reference: [Goldberg1993b]

#### Independent set

P25: Enumeration of all maximal independent sets in a chordal graph
Input: A chordal graph $G=(V,E)$.
Output: All maximal independent sets in $G$.
Complexity: $O(|V||E|\mu)$ total time.
Comment: $\mu$ is the number of maximal independent sets of $G$. This algorithm can also enumerate all the maximal cliques.
Reference: [Tsukiyama1977a]
P381: Enumeration of all maximal independent sets in a claw-free graph
Input: A claw-free graph $G$.
Output: All maximal independent sets in $G$.
Complexity:
Comment:
Reference: [Minty1980]
P376: Enumeration of all maximal independent sets in an undirected graph
Input: A graph $G$.
Output: All maximal independent sets in $G$ in lexicographically.
Complexity:
Comment:
Reference: [Loukakis1981]
P367: Enumeration of all maximal independent sets in an interval graph
Input: An interval graph $G = (V, E)$.
Output: All maximal independent sets in $G$.
Complexity: $O(|V|^2 + \beta)$ total time.
Comment: $\beta$ is the sum of the vertices in all maximal independent sets of $G$.
Reference: [Leung1984]
P368: Enumeration of all maximal independent sets in a circular-arc graph
Input: A circular-arc graph $G = (V, E)$.
Output: All maximal independent sets in $G$.
Complexity: $O(|V|^2 + \beta)$ total time.
Comment: $\beta$ is the sum of the vertices in all maximal independent sets of $G$.
Reference: [Leung1984]
P369: Enumeration of all maximal independent sets in a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All maximal independent sets in $G$.
Complexity: $O((|V| + |E|)N)$ total time.
Comment: $N$ is the number of solutions.
Reference: [Leung1984]
P29: Enumeration of all maximal independent sets in a graph
Input: A graph $G=(V,E)$.
Output: All maximal independent sets included in $G$.
Complexity: $O(n(m+n\log C))=O(n^3)$ delay and exponential space.
Comment: $C$: total number of maximal independent sets, $n$: total number of vertices, and $m$: total number of edges. Is there no polynomial space and delay algorithm?
Reference: [Johnson1988]
P76: Enumeration of all maximum independent sets of a bipartite graph
Input: A bipartite graph $B =(V, E)$.
Output: All maximum independent sets of $B$.
Complexity: $O(|V|^{2.5} + N)$.
Comment: $N$ is the number of maximum independent sets of $B$.
Reference: [Kashiwabara1992]
P335: Enumeration of all maximal independent sets on a tree in lexicographic order
Input: Tree $T = (V, E)$.
Output: All maximal independent sets on $T$ in lexicographic order.
Complexity: $O(|V|^2)$ delay with $O(|V|)$ space.
Comment:
Reference: [Chang1994a]
P306: Enumeration of all maximum independent set of a graph
Input: A graph $G = (V, E)$.
Output: All maximum independent set of $G$.
Complexity: $O(2^{0.114|E|})$ total time and polynomial space.
Comment:
Reference: [Beigel1999]
P307: Enumeration of all maximum independent set of a graph
Input: A graph $G = (V, E)$ with maximum degree 3.
Output: All maximum independent set of $G$.
Complexity: $O(2^{0.171|V|})$ total time and polynomial space.
Comment:
Reference: [Beigel1999]
P308: Enumeration of all maximum independent set of a graph
Input: A graph $G = (V, E)$ with maximum degree 4.
Output: All maximum independent set of $G$.
Complexity: $O(2^{0.228|V|})$ total time and polynomial space.
Comment:
Reference: [Beigel1999]
P309: Enumeration of all maximum independent set of a graph
Input: A graph $G = (V, E)$.
Output: All maximum independent set of $G$.
Complexity: $O(2^{0.290|V|})$ total time and polynomial space.
Comment:
Reference: [Beigel1999]
P292: Enumeration of all maximal independent sets of a graph
Input: A graph $G = (V, E)$ and a position integer $k$.
Output: Enumeration of all maximal independent sets with at most size $k$ of $G$.
Complexity: $O(3^{4k-|V|} 4^{|V|-3k})$ total time.
Comment:
Reference: [Eppstein2003a]
P283: Enumeration of all independent sets in a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All independent sets in $G$.
Complexity: Constant time per solution on average after $O(|V| + |E|)$ time for preprocessing.
Comment:
Reference: [Okamoto2005a]
P284: Enumeration of all independent sets of size $k$ in a chordal graph
Input: A chordal graph $G = (V, E)$ and a positive integer $k$.
Output: All independent sets of size $k$ in $G$.
Complexity: Constant time per solution on average after $O((|V| + |E|)|V|^2)$ time for preprocessing.
Comment:
Reference: [Okamoto2005a]
P285: Enumeration of all maximum independent sets in a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All maximum independent sets in $G$.
Complexity: Constant time per solution on average after $O((|V| + |E|)|V|^2)$ time for preprocessing.
Comment:
Reference: [Okamoto2005a]
P26: Enumeration of all independent sets in an input chordal graph
Input: A chordal graph $G=(V,E)$.
Output: All independent sets in $G$.
Complexity: $O(1)$ delay and $O(|V|(|V|+|E|))$ time and space for preprocessing.
Comment: Counting all independent sets in an input chordal graph needs $O(n+m)$ time.
Reference: [Okamoto2008]
P27: Enumeration of all maximum independent sets in an input chordal graph
Input: A chordal graph $G=(V,E)$.
Output: All maximum independent sets in $G$.
Complexity: $O(1)$ delay and $O(|V|(|V|+|E|))$ time and space for preprocessing.
Comment: Counting all maximum independent sets in an input chordal graph needs $O(n+m)$ time.
Reference: [Okamoto2008]
P28: Enumeration of all independent sets with $k$ vertices in an input chordal graph
Input: A chordal graph $G=(V,E)$ and an integer $k$.
Output: All maximum independent sets with $k$ vertices in $G$.
Complexity: $O(1)$ delay and $O(k|V|(|V|+|E|))$ time and space for preprocessing.
Comment: The number of independent sets with $k$ vertices in an input chordal graph needs $O(k^2(|V|+|E|))$ time.
Reference: [Okamoto2008]

#### Interval graph

P273: Enumeration of all interval supergraph that contains a given graph
Input: A graph $G = (V, E)$.
Output: All interval supergraphs each of which contain $G$.
Complexity: $O(|V|^3)$ time for each and $O(|V|^2)$ space.
Comment:
Reference: [Kiyomi2006a]
P274: Enumeration of all interval graph of a given graph
Input: A graph $G = (V, E)$.
Output: All interval graphs of $G$.
Complexity: $O((|V|+|E|)^2)$ time for each.
Comment:
Reference: [Kiyomi2006a]
P123: Enumeration of Proper Interval Graphs
Input: An integer $n$.
Output: All proper interval graphs with $n$ vertices.
Complexity: $O(1)$ time per proper interval graph and $O(n)$ space, after $O(n^2)$ preprocessing time.
Comment: Preprocessing: generating the complete graph with $n$ vertices.
Reference: [Saitoh2010]

#### Matching

P57: Enumeration of the $k$ best perfect matchings of a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ best perfect matchings of $G$ in order.
Complexity: $O(k|V|^3)$ total time.
Comment:
Reference: [Chegireddy1987]
P69: Enumeration of all stable marriage
Input: A graph $G = (V, E)$.
Output: All stable marriage of $G$.
Complexity: $O(|V|)$ time per solution and $O(|V|^2)$ space.
Comment: I'm looking for this paper.
Reference: [Gusfield1989]
P63: Enumeration of all minimum cost perfect matchings in an weighted bipartite graph
Input: An weighted bipartite graph $B = (V, E)$.
Output: All minimum cost perfect matchings in $B$.
Complexity: $O(|V|(|V| + |E|))$ time per solution and $O(|V| + |E|)$ space
Comment: I'm looking for this paper.
Reference: [Fukuda1992]
P64: Enumeration of all perfect matchings in a bipartite graph
Input: A bipartite graph $B = (U, V, E)$, where $|U| = |V|$.
Output: All perfect matchings in $B$.
Complexity: $O(c(|V| + |E|))$ total time and $O(|V| + |E|)$ space, after $O(n^{2.5})$ preprocessing time.
Comment: $c$ is the number of solutions.
Reference: [Fukuda1994]
P85: Enumeration of the $k$ best perfect matchings of a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ best perfect matchings of $G$ in decreasing order.
Complexity: $O(k|V|^3)$ total time with $O(k|V|^2)$ space.
Comment:
Reference: [Matsui1994]
P32: Enumeration of all perfect, maximum, and maximal matchings in bipartite graphs
Input: A bipartite graph $B=(V, E)$.
Output: All perfect, maximum, and maximal matching in $B$.
Complexity: $O(|V|)$ time per matching.
Comment:
Reference: [Uno1997]
P116: Enumeration of all maximal matchings in a graph
Input: A graph $G = (V, E)$.
Output: All maximal matchings in $G$.
Complexity: $O(|V| + |E| + \Delta N)$ total time and $O(|V| + |E|)$ space.
Comment: $N$ is the number of solutions and $\Delta$ is the maximum degree in $G$. I'm looking for this paper.
Reference: [Uno2001]
P132: Enumeration of all minimal blocker in a bipartite graph
Input: A bipartite graph $G = (U, V, E)$.
Output: All minimal blocker in $G$.
Complexity: Polynomial delay and space.
Comment: A \textit{blocker} of $G$ is an edge subset $X$ of $E$ such that $G' = (U, V, E \setminus X)$ has no perfect matching. I'm looking for this paper.
Reference: [Boros2006]
P133: Enumeration of all basic perfect 2-matchings in a graph
Input: A graph $G = (V, E)$.
Output: All basic perfect 2-matchings in $G$.
Complexity: Incremental polynomial delay.
Comment: A \textit{basic 2-matching} of $G$ is a subset of edges that cover the vertices with vertex-disjoint edges and vertex-disjoint odd cycles. I'm looking for this paper.
Reference: [Boros2006]
P134: Enumeration of all $d$-factor in a bipartite graph
Input: A bipartite graph $G = (U, V, E)$ and any non negative function $d: A \cup B \to \{0, 1, \cdots, |U| + |V|\}$.
Output: All $d$-factor in $G$.
Complexity: $O(|E|)$ delay.
Comment: A $d$-factor in $G$ is a subgraph $G' = (U, V, X)$ covering all vertices of $G$, whose each vertex $v$ has degree $d(v)$. If for any $v \in U \cup V$, $d(v) = 1$, $G'$ is a perfect matching. I'm looking for this paper.
Reference: [Boros2006]
P424: Enumeration of all maximal induced matchings in a triangle-free graph
Input: A triangle-free graph $G$.
Output: All maximal induced matchings in $G$.
Complexity: $O(1.4423^n)$ total time with polynomial delay.
Comment: $n$ is the number of vertices in $G$.
Reference: [Basavaraju2014]

#### Matroid

P117: Enumeration of all bases of a graphic matroid in a graph
Input: A graph $G = (V, E)$.
Output: All bases of a graphic matroid in $G$.
Complexity: $O(|V| + |E| + N)$ total time and $O(|V| + |E|)$ space.
Comment: $N$ is the number of solutions. If $G$ is connected, any base is a spanning tree.
Reference: [Uno1998]
P118: Enumeration of all bases of a linear matroid in a graph
Input: A graph $G = (V, E)$.
Output: All bases of a linear matroid in $G$.
Complexity: $O(|V|)$ time per solution and $O(|V|^2|E|)$ preprocessing after time.
Comment:
Reference: [Uno1998]
P119: Enumeration of all bases of a matching matroid in a graph
Input: A graph $G = (V, E)$.
Output: All bases of a matching matroid in $G$.
Complexity: $O(|V| + |E|)$ time per solution.
Comment:
Reference: [Uno1998]

#### Ordering

P78: Enumeration of all topological sortings of a directed graph
Input: A directed graph $G =(V, E)$.
Output: All topological sortings of $G$.
Complexity: $O(|V| + |E|)$ time per sorting and $O(|V| + |E|)$ space.
Comment:
Reference: [Knuth1974]
P386: Enumeration of all topological sortings of a given set in lexicographically
Input: An $n$-element set $S$.
Output: All topological sortings of $S$ in lexicographically.
Complexity: $O(m)$ time per solution(?).
Comment:
Reference: [Knuth1979]
P378: Enumeration of all topological sortings of a po set
Input: A partial order set $P$.
Output: All topological sortings of $P$.
Complexity: $O(|P|)$ time per solution.
Comment: $|P|$ is the number of objects in $P$.
Reference: [Varol1981]
P349: Enumeration of all topological sortings in a directed acyclic graph
Input: A directed graph $G$.
Output: All topological sortings in $G$.
Complexity: $O(1)$ amortized time per solution with $O(|G|)$.
Comment: Linear extensions correspond to topological sortings.
Reference: [Pruesse1991a]
P346: Enumeration of all topological sortings
Input: A graph $G$.
Output: All topological sortings in $G$.
Complexity: $O(1)$ amortized time per solution.
Comment: A topological sorting is also known as a linear extension.
Reference: [Ruskey1992a]
P101: Enumeration of all topological sortings
Input: A directed acyclic graph $D$.
Output: All topological sortings $D$.
Complexity: $O(1)$ amortized time per topological sorting and $O(|V|)$ space in addition to the space used for $D$.
Comment: Linear sortings correspond to topological sortings.
Reference: [Pruesse1994]
P331: Enumeration of all linear extensions of a given poset
Input: A poset $P$.
Output: All linear extensions of $P$.
Complexity: $O(1)$ time per solution.
Comment: Their algorithm is a loop-free algorithm.
Reference: [Canfield1995]
P326: Enumeration of all topological sortings of an acyclic directed graph
Input: An acyclic directed graph $G = (V, E)$.
Output: All topological sortings of $G$.
Complexity: $O(|V|N)$ total time and $O(|V||E|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Avis1996]
P291: Enumeration of all perfect elimination orderings
Input: A chordal graph $G$.
Output: All perfect elimination orderings of $G$.
Complexity: Constant amortized time per solution.
Comment:
Reference: [Chandran2003]
P295: Enumeration of all forest extensions of a partially ordered set
Input: A partially ordered set $P$.
Output: All forest extensions of $P$.
Complexity: $O(|E|^2)$ delay and $O(|E||R|)$ space.
Comment: $E$ is the set of elements. $R$ is the binary relation on $E$.
Reference: [Szwarcfiter2003b]
P39: Enumeration of all topological sortings of a directed acyclic graph
Input: A directed acyclic graph $D$.
Output: All topological sortings $D$.
Complexity: $O(1)$ delay per topological sorting.
Comment: Linear extensions correspond to topological sortings.
Reference: [Ono2005]
P175: Enumeration of all realizer of a triangulated planar graph
Input: A triangulated planar graph $G = (V, E)$.
Output: All realizer of $G$.
Complexity: $O(|V|)$ time per realizer.
Comment: I'm looking for this paper.
Reference: [Yamanaka2006]
P241: Enumeration of all perfect elimination orderings of a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All perfect elimination orderings of $G$.
Complexity: $O(1)$ time per solution on average with $O(|V|^2)$ space and $O(|V|^3)$ with $O(|V|^2)$ space pre-computation.
Comment:
Reference: [Matsui2008]
P38: Enumeration of all perfect sequences in a chordal graph
Input: A chordal graph $G = (V, E)$.
Output: All perfect sequences of $G$.
Complexity: $O(1)$ time per graph with $O(|V|^2)$ space with $O(|V|^3)$ time and $O(|V|^2)$ space pre-computation.
Comment:
Reference: [Matsui2010]

#### Orientation

P305: Enumeration of all acyclic orientation of a graph
Input: A graph $G = (V, E)$.
Output: All acyclic orientation of $G$.
Complexity: $O(N(|V|+|E|))$ total time ($O(|V|(|V|+E|))$ delay) and $O(|V| + |E|)$ space.
Comment: A acyclic orientation of $G$ is an assignment of directions of each edge such that $G$ is acyclic.
Reference: [Barbosa1999]
P174: Enumeration of all $(s, t)$-orientations of a biconnected planar graph
Input: A biconnected planar graph $G = (V, E)$ and an edge $(s, t)$ in $G$.
Output: All $(s, t)$-orientations of $G$.
Complexity: $O(|V|)$ time per solution.
Comment: I'm looking for this paper.
Reference: [Setiawan2011]

#### Other

P417: Enumeration of all Hamiltonian centers in a graph
Input: A graph $G$.
Output: All Hamiltonian centers in $G$.
Complexity:
Comment:
Reference: [Yau1967]
P347: Enumeration of all CA-sets of a directed graph
Input: Directed graph $G = (V, E)$.
Output: All CA-sets of $G$.
Complexity: $O(|V|^{2.49+} + \gamma)$.
Comment: $\gamma$ is the output size. $S \subset V$ is a \textit{CA-set} if, for each $v \in S$, all ancestor of $v$ belongs to $S$.
Reference: [Kashiwabara1992]
P253: Enumeration of all maximal induced subgraphs for (connected) hereditary graph properties
Input: A graph $G$.
Output: All maximal induced subgraphs in $\mathcal{P}(G)$.
Complexity: See the paper.
Comment: $\mathcal{P}$ is a set of subgraphs of $G$ with (connected) hereditary graph properties.
Reference: [Cohen2008]

#### Path

P394: Enumeration of all simple paths in a graph
Input: A graph $G$.
Output: All simple paths in $G$.
Complexity:
Comment:
Reference: [Ponstein1966]
P419: Enumeration of all Hamiltonian paths in a graph
Input: A graph $G$.
Output: All Hamiltonian paths in $G$.
Complexity:
Comment:
Reference: [Yau1967]
P421: Enumeration of all directed paths in a directed graph
Input: A directed graph $G$.
Output: All directed paths in $G$.
Complexity:
Comment:
Reference: [Kamae1967]
P423: Enumeration of all paths in a graph
Input: A graph $G$.
Output: All paths in $G$.
Complexity:
Comment:
Reference: [Kroft1967b]
P416: Enumeration of all paths in a graph
Input: A graph $G$.
Output: All paths in $G$.
Complexity:
Comment:
Reference: [Danielson1968]
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: I'm looking for this paper.
Reference: [Yen1971]
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. I'm looking for this paper.
Reference: [Lawler1972]
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:
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:
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: I'm looking for this paper.
Reference: [Shier1979]
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]
P178: Enumeration of all shortest paths in a graph
Input: A graph $G$.
Output: All shortest paths in $G$.
Complexity:
Comment: I'm looking for this paper.
Reference: [Florian1981]
P179: Enumeration of all shortest paths in a graph
Input: A graph $G = (V, E)$.
Output: All shortest paths in $G$.
Complexity: $O(M(|V|) + |V|^2)$ total time.
Comment: $M(n)$ is the time complexity of the best algorithm for $n\times n$ matrix multiplication.
Reference: [Watanabe1981]
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]
P350: 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]
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]
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]
P336: Enumeration of all constrained quickest paths in a network
Input: 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]
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]
P287: 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]
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]
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]
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]
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]
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]
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]

#### Permutation graph

P37: Enumeration of all connected bipartite permutation graphs with $n$ vertices
Input: A graph size $n$.
Output: All connected bipartite permutation graphs.
Complexity: $O(1)$ time per graph with $O(n)$ space.
Comment:
Reference: [Saitoh2010]

#### Pitch

P200: Enumeration of all stories in a graph
Input: A directed graph $G = (V, E, S, T)$ that has the set of source vertices $S$ and the set of target vertices of $T$.
Output: All stories in $G$.
Complexity:
Comment: A \textit{pitch} $P$ of $G$ is a set of arcs $E' \subseteq E$, such that the subgraph $G′ =(V', E′)$ of $G$, where $V' \subseteq V$ is the set of vertices of G having at least one out-going or in-coming arc in $E'$, is acyclic and for each vertex $w \in V' \setminus S$, $w$ is not a source in $G'$, and for each vertex $w \in V' \setminus T$ ,$w$ is not a target in $G'$. $P$ is a \textit{story} if $P$ is maximal.
Reference: [Acuna2012]
P16: Enumeration of all pitches
Input: A directed graph $G = (V, E, S, T)$ that has the set of source vertices $S$ and the set of target vertices of $T$.
Output: All pitches in $G$.
Complexity: $O(|V| + |E|)$ delay with $O(|V| + |E|)$ space.
Comment: A pitch $P$ of $G$ is a set of arcs $E' \subseteq E$, such that the subgraph $G′ =(V', E′)$ of $G$, where $V' \subseteq V$ is the set of vertices of G having at least one out-going or in-coming arc in $E'$, is acyclic and for each vertex $w \in V' \setminus S$, $w$ is not a source in $G'$, and for each vertex $w \in V' \setminus T$ ,$w$ is not a target in $G'$. Enumeration of all stories (maximal pitches) is still open.
Reference: [Borassi2013]

#### Planar graph

P147: Enumeration of all maximal planar graphs with $n$ vertices
Input: An integer $n$.
Output: All maximal planar graph with $n$ vertices.
Complexity: $O(n^3)$ time per graph with $O(n)$ space.
Comment: A planar graph with $n$ vertices is \textit{maximal} if it has exactly $3n -6$ edges.
Reference: [Nakano2004a]
P155: Enumeration of all based floorplans with at most $n$ faces
Input: An integer $n$.
Output: All based floorplans with at most $n$ faces.
Complexity: $O(1)$ time per solution with $O(n)$ space.
Comment: A planar graph is called a \textit{floorplan} if every face is a rectangle. A \textit{based floorplan} is a floorplan with one designated base line segment on the outer face.
Reference: [Nakano2001a]
P156: Enumeration of all based floorplans with exactly $n$ faces
Input: An integer $n$.
Output: All based floorplans with exactly $n$ faces.
Complexity: $O(1)$ time per solution with $O(n)$ space.
Comment: A planar graph is called a \textit{floorplan} if every face is a rectangle. A \textit{based floorplan} is a floorplan with one designated base line segment on the outer face.
Reference: [Nakano2001a]
P157: Enumeration of all floorplans with exactly $n$ faces
Input: An integer $n$.
Output: All floorplans with exactly $n$ faces.
Complexity: $O(1)$ time per solution with $O(n)$ space.
Comment: A planar graph is called a \textit{floorplan} if every face is a rectangle.
Reference: [Nakano2001a]
P220: Enumeration of all internally triconnected planar graphs
Input: Integers $n$ and $g$.
Output: All internally triconnected planar graphs with exactly $n$ vertices such that $\kappa(G) = 2$ and the size of each inner face is at most $g$.
Complexity: $O(n^3)$ time per solution on average with $O(n)$ space.
Comment:
Reference: [Zhuang2010a]

#### Plane graph

P255: Enumeration of all plane straight-line graphs on a given point set in the plane
Input: A point set $P$ in the plane.
Output: All plane straight-line graphs on $P$.
Complexity: $O(|P|\log|P|)$ time per solution.
Comment: Use gray code.
Reference: [Aichholzer2007]
P256: Enumeration of all plane and connected straight-line graphs on a given point set in the plane
Input: A point set $P$ in the plane.
Output: All plane and connected straight-line graphs on $P$.
Complexity: $O(|P|\log|P|)$ time per solution.
Comment: Use gray code.
Reference: [Aichholzer2007]
P257: Enumeration of all plane spanning trees on a given point set in the plane
Input: A point set $P$ in the plane.
Output: All plane spanning trees on $P$.
Complexity: $O(|P|\log|P|)$ time per solution.
Comment: Use gray code.
Reference: [Aichholzer2007]
P17: Enumeration of all plane graphs
Input: $m$: the maximum number of edges.
Output: All connected rooted plane graphs with at most $m$ edges.
Complexity: amortized $O(1)$ time per graph with $O(m)$ space.
Comment: This algorithm does not outputs the entire graph but the difference from previous one.
Reference: [Yamanaka2009]
P18: Enumeration of all plane graphs
Input: $m$: the maximum number of edges.
Output: All connected non-rooted plane graphs with at most $m$ edges.
Complexity: $O(m^3)$ time per graph with $O(m)$ space.
Comment: This algorithm does not outputs the entire graph but the difference from previous one.
Reference: [Yamanaka2009]
P248: Enumeration of all plane graphs on a given point set in the plane
Input: A fixed point set $P$.
Output: All plane graphs on $P$.
Complexity: $O(N)$ total time.
Comment: $N$ is the number of solutions.
Reference: [Katoh2009a]
P249: Enumeration of all non-crossing spanning connected graphs on a given point set in the plane
Input: A fixed point set $P$.
Output: All non-crossing spanning connected graphs on $P$.
Complexity: $O(N)$ total time.
Comment: $N$ is the number of solutions.
Reference: [Katoh2009a]
P250: Enumeration of all non-crossing spanning trees on a given point set in the plane
Input: A fixed point set $P$.
Output: All non-crossing spanning trees on $P$.
Complexity: $O(N + |P|tri(P))$ total time.
Comment: $N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.
Reference: [Katoh2009a]
P251: Enumeration of all non-crossing minimally rigid frameworks on a given point set in the plane
Input: A fixed point set $P$.
Output: All non-crossing minimally rigid frameworks on $P$.
Complexity: $O(|P|^2N)$ total time.
Comment: $N$ is the number of solutions.
Reference: [Katoh2009a]
P252: Enumeration of all non-crossing perfect matchings on a given point set in the plane
Input: A fixed point set $P$.
Output: All non-crossing perfect matchings on $P$.
Complexity: $O(|P|^{3/2}tri(P) + |P|^{5/2}N)$ total time.
Comment: $N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.
Reference: [Katoh2009a]
P208: Enumeration of all triconnected rooted plane graphs
Input: Integers $n$ and $g$.
Output: All triconnected rooted plane graphs with $n$ vertices, whose each inner face has the length at most $g$.
Complexity: $O(1)$ delay with $O(n)$ space after $O(n)$ time preprocessing.
Comment:
Reference: [Zhuang2010]
P209: Enumeration of all triconnected rooted plane graphs
Input: An integer $n$.
Output: All triconnected rooted plane graphs with $n$ vertices.
Complexity: $O(n^3)$ delay with $O(n)$ space after $O(n)$ time preprocessing.
Comment:
Reference: [Zhuang2010]
P215: Enumeration of all biconnected rooted plane graphs
Input: Integers $n$ and $g$.
Output: All biconnected rooted plane graphs with exactly $n$ vertices such that each inner face is of length at most $g$.
Complexity: $O(1)$ delay with $O(n)$ space, after an $O(n)$ time preprocessing.
Comment:
Reference: [Zhuang2010c]
P216: Enumeration of all biconnected plane graphs
Input: Integers $n$ and $g$.
Output: All biconnected plane graphs with at most $n$ vertices such that each inner face is of length at most $g$.
Complexity: $O(n^3)$ time per solution on average with $O(n)$ space.
Comment:
Reference: [Zhuang2010c]
P217: Enumeration of all biconnected rooted plane graphs
Input: Integers $n$ and $g$.
Output: All biconnected rooted plane graphs with at most $n$ vertices such that each inner face is of length at most $g$.
Complexity: $O(1)$ delay with $O(n)$ space.
Comment:
Reference: [Zhuang2010c]
P219: Enumeration of all rooted plane graphs in $\mathcal{G}_{\text{int}}(n, g) - \mathcal{G}_3(n, g)$
Input: Integers $n$ and $g$.
Output: All rooted plane graphs in $\mathcal{G}_{\text{int}}(n, g) - \mathcal{G}_3(n, g)$
Complexity: $O(1)$ delay with $O(n)$ space and time preprocessing.
Comment:
Reference: [Zhuang2010a]

#### Polytope

P340: Enumeration of all 3-polytopes of a graph
Input: A graph $G = (V, E)$.
Output: All 3-polytopes of $G$.
Complexity:
Comment:
Reference: [Deza1993]

P183: Enumeration of all quadrangles in a graph
Input: A connected graph $G = (V, E)$.
Output: All quadrangles in $G$.
Complexity: $O(\alpha(G)|E|)$ total time and $O(|E|)$ space.
Comment: $\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed. I'm looking for this paper.
Reference: [Chiba1985]

P168: Enumeration of all based biconnected plane quadrangulations with at most $f$ faces
Input: An integer $f$.
Output: All based biconnected plane quadrangulations with at most $f$ faces.
Complexity: $O(1)$ time per quadrangulation and $O(f)$ space.
Comment: A \textit{plane quadrangulation} is a plane graph such that each inner face has exactly four edges on its contour. A \textit{based plane quadrangulation} is a plane quadrangulation with one designated edge on the outer face. I'm looking for this paper.
Reference: [Li2003]

#### Regular graph

P427: Enumeration of all cubic graphs with less than or equal to $n$ vertices
Input: An integer $n$.
Output: All cubic graphs with less than or equal to $n$ vertices.
Complexity:
Comment:
Reference: [Brinkmann2011]

#### Series-parallel

P165: Enumeration of all series-parallel graphs with at most $m$ edges
Input: An integer $m$.
Output: All series-parallel graphs with at most $m$ edges.
Complexity: $O(m)$ time per graph.
Comment:
Reference: [Kawano2005]

#### Spanning subgraph

P138: Enumeration of all minimal $k$-vertex connected spanning subgraphs in a $k$-connected graph.
Input: A $k$-connected graph $G$.
Output: All minimal $k$-vertex connected spanning subgraphs in $G$.
Complexity: $O(K^3|E|^3|n| + K^2|E|^5|V|^4 + K|V|^k|E|^2)$ total time.
Comment: $K$ is the number of solutions. A graph $G$ is $k$-connected if a subgraph of $G$ obtained by removing at most $k-1$ vertices is still connected.
Reference: [Boros2007]

#### Spanning tree

P392: Enumeration of all spanning trees in a graph
Input: A graph $G$.
Output: All spanning trees in $G$.
Complexity:
Comment:
Reference: [Hakimi1961]
P1: Enumeration of all spanning trees in a graph
Input: A graph $G=(V,E)$.
Output: All spanning trees of $G$.
Complexity:
Comment: In this paper, 'trees' indicate 'spanning trees'.
Reference: [Minty1965]
P384: Enumeration of all spanning trees of a graph
Input: A graph $G$.
Output: All spanning trees of $G$.
Complexity:
Comment:
Reference: [Mayeda1965a]
P102: Enumeration of all spanning trees in a graph
Input: A graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(|V||E|^2)$ time per spanning tree with $O(|V||E|)$ space.
Comment:
P51: Enumeration of the $k$ smallest weight spanning trees in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ smallest weight spanning trees in $G$.
Complexity: $O(k|E|\alpha (|E|,|V|) + |E|\log |E|)$ total time and $O(k + |E|)$ space, $\alpha(\cdot)$ is Tarjan's inverse of Ackermann's function.
Comment:
Reference: [Gabow1977]
P52: Enumeration of all spanning trees in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The all spanning trees in $G$ in order.
Complexity: $O(N|V|)$ total time and $O(N + |E|)$ space, $N$ is the number of spanning trees in $G$.
Comment:
Reference: [Gabow1977]
P67: Enumeration of all spanning trees in an undirected graph
Input: An undirected graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(|V| + |E| + |V|N)$ total time and $O(|V| + |E|)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Gabow1978]
P68: Enumeration of all spanning trees in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(|V| + |E| + |E|N)$ total time and $O(|V| + |E|)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Gabow1978]
P55: Enumeration of the $k$ smallest weight spanning trees in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ smallest weight spanning trees in $G$.
Complexity: $O(k|E| + \min (|V|^2 ,|E|\log \log |V|))$ total time and $O(k + |E|)$ space
Comment:
Reference: [Katoh1981]
P371: Enumeration of all spanning trees in an undirected graph
Input: An undirected graph $G$.
Output: All spanning trees in $G$.
Complexity:
Comment: They analized Char's enumeration algorithm.
Reference: [Jayakumar1984]
P53: Enumeration of the $k$ smallest weight spanning trees in a graph in increasing order
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ smallest weight spanning trees in $G$.
Complexity: $O(|E|\log\log_{(2+|E|/|V|)} n + k^2\sqrt{|E|})$ total time and $O(|E| + k\sqrt{|E|})$ space.
Comment:
Reference: [Frederickson1985]
P54: Enumeration of the $k$ smallest weight spanning trees in a planar graph in increasing order
Input: A planar graph $G = (V, E)$ and an integer $k$.
Output: The $k$ smallest weight spanning trees in $G$.
Complexity: $O(|V| + k^2(\log |V|)^2)$ total time and $O(|V| + k(\log |V|)^2)$ space.
Comment:
Reference: [Frederickson1985]
P362: Enumeration of all undirected minimum spanning trees in an undirected graph
Input: An undirected graph $G = (V, E)$.
Output: All undirected minimum spanning trees in $G$.
Complexity: $O(|E|\log \beta(|E|, |V|))$ total time.
Comment: $\beta(|E|, |V|) = \min\{i | \log^{(i)}|V| \le |E|/|N|\}$.
Reference: [Gabow1986a]
P363: Enumeration of all directed minimum spanning trees in an directed graph
Input: A directed graph $G = (V, E)$.
Output: All directed minimum spanning trees in $G$.
Complexity: $O(|V|\log \beta(|E|, |V|))$ total time.
Comment: $\beta(|E|, |V|) = \min\{i | \log^{(i)}|V| \le |E|/|N|\}$.
Reference: [Gabow1986a]
P73: Enumeration of all spanning tree in a graph
Input: A graph $G = (V, E)$.
Output: All spanning tree of $G$.
Complexity: $O(|V|+|E|+N)$ total time and $O(|V||E|)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Kapoor1991]
P74: Enumeration of all spanning tree in an weighted graph
Input: An weighted graph $G = (V, E)$.
Output: All spanning tree of $G$ in increasing order of weight.
Complexity: $O(N\log |V|+|V||E|)$ total time and $O(N + |V|^2|E|)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Kapoor1991]
P75: Enumeration of all spanning tree in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All spanning tree of $G$.
Complexity: $O(N|V|+|V|^3)$ total time and $O(|V|^2)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Kapoor1991]
P47: Enumeration of the $k$ best spanning trees in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ best spanning trees of $G$.
Complexity: $O(m\log\beta(|E|, |V|) + k^2)$ total time.
Comment: $\beta(|E|, |V|) = \min \{\log^{(i)}|V| \le |E|/|V|\}$.
Reference: [Eppstein1992]
P48: Enumeration of the $k$ best spanning trees in a planar graph
Input: A planar graph $G = (V, E)$ and an integer $k$.
Output: The $k$ best spanning trees of $G$.
Complexity: $O(n + k^2)$ total time
Comment:
Reference: [Eppstein1992]
P88: Generation of the $k$-th minimum spanning tree in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$-th minimum spanning tree of $G$.
Complexity: $O((|V||E|)^{k-1})$ time.
Comment:
Reference: [Mayr1992]
P110: Enumeration of all spanning trees
Input: A graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(N + |V| + |E|)$ total time and $O(|V||E|)$ space.
Comment: $N$ is the number of spanning trees in $G$.
Reference: [Shioura1995]
P301: Enumeration of all spanning trees in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: INCORRECT: $O(N \log |V| + |V|^2\alpha(V, V) + |V||E|)$
Comment: $\alpha$: the inverse Ackermann's function. [KR2000] gives this result is wrong.
Reference: [Hariharan1995]
P115: Enumeration of all spanning trees in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(¦E¦+ND(¦V¦, ¦E¦))$ total time and $O(¦E¦+DS(¦V¦, ¦E¦))$ space.
Comment: $D(¦V¦, ¦E¦)$ and $DS(¦V¦, ¦E¦)$ are the time and space complexities of the data structure for updating the minimum spanning tree in an undirected graph with $¦V¦$ vertices and $¦E¦$ edges. Here $N$ denotes the number of directed spanning trees in $G$.
Reference: [Uno1996]
P15: Enumeration of all spanning trees in a graph
Input: A graph $G=(V,E)$.
Output: All spanning trees included in $G$.
Complexity: $O(N+|V|+|E|)$ total time and $O(|V|+|E|)$ space.
Comment: $N$ = number of spanning trees in $G$.
Reference: [Shioura1997]
P59: Enumeration of the $k$ smallest weight spanning trees in a graph
Input: A graph $G = (V, E)$ and an integer $k$.
Output: The $k$ smallest weight spanning trees in $G$.
Complexity: $O(m \log \log* n + k \min(n, k)^{1/2})$ total time, or a randomized version taking $O(m + k \min(n, k)^{1/2})$ total time.
Comment:
Reference: [Eppstein1997]
P83: Enumeration of all spanning trees in a graph
Input: A graph $G = (V, E)$.
Output: All spanning trees in $G$.
Complexity: $O(|V| + |E| + \tau)$ time and $O(|V| + |E|)$ space (depth first manner) or $O(\tau|V| + |E|)$ space (breadth first manner).
Comment: By using breadth first manner, the proposed algorithm can be used in a parallel computer.
Reference: [Matsui1997]
P84: Enumeration of all spanning trees in a graph in non-decreasing order
Input: A graph $G = (V, E)$.
Output: All spanning trees in $G$ in non-decreasing order.
Complexity: $O(|V| + |E| + \tau)$ time and $O(\tau|V| + |E|)$ space.
Reference: [Matsui1997]
P120: Enumeration of all directed spanning trees in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All directed spanning trees in $G$.
Complexity: $O(|E| \log |V| + |V| + N \log^2 |V|)$ total time and $O(|E| + |V|)$ space.
Comment: $N$ is the number of directed spanning trees.
Reference: [Uno1998a]
P286: Enumeration of all spanning trees of an weighted graph in order of increasing cost
Input: An weighted graph $G = (V, E)$.
Output: All spanning trees of $G$ in order of increasing cost.
Complexity: $O(N|E|\log |E| + N^2)$ total time and $O(N|E|)$ space.
Comment: $N$ is the number of spanning trees of $G$.
Reference: [Sorensen2005]
P214: Enumeration of all the minimum spanning trees in a graph
Input: An weighted graph $G = (V, E)$.
Output: All the minimum spanning trees in $G$.
Complexity: $O(N|E|\log|V|)$ total time and $O(|E|)$ space.
Comment: $N$ is the number of the minimum spanning trees in $G$.

#### Steiner tree

P263: Enumeration of all Steiner $W$-trees in a connected graph
Input: A connected graph $G = (V, E)$, a vertex set $W \subseteq V$ such that $|W| = k$, for a fixed integer $k$.
Output: Enumeration of all Steiner $W$-trees in $G$.
Complexity: $O(|V|^2(|V|+|E|) + |V|^{k-2} + N|V|)$ total time with $O(|V|^{k-2} + |V|^2(|V| + |E|))$ space.
Comment: A connected subgraph $T$ of $G$ is a Steiner $W$-tree if $W \subseteq V(T)$ and $|E(T)$ is minimum.

#### Subforest

P432: Enumeration of all $k$-trees in a graph
Input: A graph $G = (V, E)$.
Output: All $k$-trees in $G$.
Complexity:
Comment: A $k$-tree is a forest with $k$ connected components.
Reference: [Hakimi1964]

#### Subgraph

P325: 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]
P299: 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]
P234: Enumeration of all minimal spanning graph
Input: A graph $G = (V, E)$, $S \subseteq V$, and requirements $r(u, v)$ for all $(u, v) \in V \times V$.
Output: All minimal spanning graph $H$ of $G$ satisfying $\lambda^S_H \ge r(u, v) \; \forall (u, v) \in V \times V$.
Complexity: Incremental polynomial time.
Comment: The $S$-connectivity $\lambda^S_G(u, v)$ of $(u, v)$ in $G$ is the maximum number of $uv$-paths such that no two of them have an edge or a node in $S − \{u, v\}$ in common. This complexity holds for edge-connectivity.
Reference: [Nutov2009]
P235: Enumeration of all $k$-outconnected minimal spanning graph
Input: A graph $G = (V, E)$, a vertex $s \in V$, and an integer $k$.
Output: All minimal $k$-outconneted from $s$ spanning subgraph of $G$.
Complexity: Incremental polynomial time.
Comment: A graph is $k$-outconnected from $s$ if it contains $k$ internally-disjoint $st$-paths for every $t \in V$. This complexity holds for both vertex and edge-connectivity.
Reference: [Nutov2009]
P236: Enumeration of all $k$-outconnected minimal spanning graph
Input: A directed graph $G = (V, E)$, a vertex $s \in V$, and an integer $k$.
Output: All minimal $k$-outconneted from $s$ spanning subgraph of $G$.
Complexity: Incremental polynomial time.
Comment: A graph is $k$-outconnected from $s$ if it contains $k$ internally-disjoint $st$-paths for every $t \in V$. This complexity holds for both vertex and edge-connectivity.
Reference: [Nutov2009]
P237: Enumeration of all $k$-connected minimal spanning graph
Input: A directed graph $G = (V, E)$ and an integer $k$.
Output: All minimal $k$-connected spanning subgraph of $G$.
Complexity: Incremental polynomial time.
Comment: This complexity holds for both vertex and edge-connectivity.
Reference: [Nutov2009]

#### Subtree

P3: Enumeration of all subtrees in an input tree
Input: A tree $T=(V, E)$.
Output: All subtrees included in $T$.
Complexity: $O(|V|)$ delay and $O(|V|)$ space.
Comment:
Reference: [Ruskey1981]
P374: Enumeration of all $k$-noded subtrees in a tree
Input: A tree $T$ and an integer $k$.
Output: All $k$-noded subtrees in $T$.
Complexity:
Comment:
Reference: [Hikita1983]
P2: Enumeration of all $k$-subtrees in a graph
Input: A graph $G=(V, E)$ and a positive integer $k$.
Output: All $k$-subtrees included in $G$.
Complexity: $O(sk)$ total time, $O(k)$ amortized time per solution, and $O(|E|)$ space.
Comment: $s$ = number of $k$-subtrees in $G$, a $k$-subtree means a connected, acyclic, and edge induced subgraph with $k$ vertices.
Reference: [Ferreira2011]
P4: Enumeration of all $k$-subtrees in an input tree
Input: A tree $T=(V, E)$ and an integer $k$.
Output: All $k$-subtrees included in $T$.
Complexity: $O(1)$ delay and $O(|V|)$ space after $O(|V|)$ time preprocessing.
Comment: A $k$-subtree is a connected, acyclic, and edge induced subgraph with $k$ vertices. I'm looking for this paper.
Reference: [Wasa2012b]
P199: Enumeration of all $k$-cardinarity subtrees of a tree with $w$ vertices
Input: An integer $k$ and a tree $T$ with $w$ element, where $k \le w$.
Output: All subtrees with $k$ vertices of $T$.
Complexity: $O(Nw^5)$ total time.
Comment: $N$ is the number of ideals.
Reference: [Wild2013]
P377: Enumeration of all induced subtrees in a $k$-degenerate graph
Input: A $k$-degenerate graph $G = (V, E)$.
Output: All induced subtrees in $G$.
Complexity: $O(k)$ amortized time per solution with $O(|V| + |E|)$ space and preprocessing time.
Comment:
Reference: [Wasa2010]

#### Tour

P108: Enumeration of $k$ best solutions to the Chinese postman problem solutions
Input: A graph $G = (V, E)$.
Output: $K$ best solutions to the Chinese postman problem.
Complexity: $O(S( n,m ) + K( n + m + \log k + nT( n + m,m ) ) )$ where $S( s,t )$ denotes the time complexity of an algorithm for ordinary Chinese postman problems and $T( s,t )$ denotes the time complexity of a post-optimal algorithm for non-bipartite matching problems defined on a graph with s vertices and t edges.
Comment:
Reference: [Saruwatari1993]

#### Tree

P389: Enumeration of all binary trees with fixed number leaves in lexicographically
Input: An integer $n$.
Output: All binary trees with $n$ leaves in lexicographically.
Complexity: $O(1)$ time per binary tree.
Comment:
Reference: [Ruskey1977]
P390: Enumeration of all $t$-ary trees with fixed number leaves in lexicographically
Input: An integer $n$.
Output: All $t$-ary trees with $n$ leaves in lexicographically.
Complexity: $O(t)$ time per binary tree.
Comment:
Reference: [Ruskey1978a]
P401: Enumeration of all $k$-ary trees with $n$ vertices
Input: Integers $k$ and $n$.
Output: All $k$-ary trees with $n$ vertices
Complexity: $O(1)$ time per solution
Comment:
Reference: [Trojanowski1978]
P403: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity:
Comment:
Reference: [Rotem1978a]
P398: Enumeration of all $k$-ary trees with $n$ vertices
Input: Integers $k$ and $n$.
Output: All $k$-ary trees with $n$ vertices
Complexity:
Comment:
Reference: [Zaks1979]
P379: Enumeration of all rooted trees with $n$ vertices
Input: An integer $n$.
Output: All rooted trees with $n$ vertices.
Complexity: $O(1)$ amortized time per solution.
Comment:
Reference: [Beyer1980]
P380: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity:
Comment:
Reference: [Proskurowski1980]
P385: Enumeration of all $k$-ary trees in lexicographically
Input: An integer $n$.
Output: All $k$-ary trees with $n$ internal vertices in lexicographically
Complexity: $O(1- (k-1)^{k-1}/k^k)^{-1}$ time per solution. This limit is $4/3$ for the binary case.
Comment:
Reference: [Zaks1980]
P375: Enumeration of all regular $k$-ary trees with $n$ ndoes
Input: Integers $k$ and $n$.
Output: All regular $k$-ary trees with $n$ ndoes.
Complexity:
Comment:
Reference: [Zaks1982]
P359: Enumeration of all binary trees with $n$ vertices in the lexicographic ordering
Input: An integer $n$.
Output: All binary trees with $n$ vertices in the lexicographic ordering
Complexity: $O(1)$ time per solution on average.
Comment:
Reference: [Zerling1985]
P364: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity: $O(n)$ time per solution.
Comment:
Reference: [Proskurowski1985]
P366: Enumeration of all ordered trees with $n$ internal vertices
Input: An integer $n$.
Output: All ordered trees with $n$ internal vertices.
Complexity:
Comment:
Reference: [Er1985]
P358: Enumeration of all free trees with $n$ vertices
Input: An integer $n$.
Output: All free trees with $n$ vertices.
Complexity: $O(1)$ time per solution.
Comment:
Reference: [Wright1986]
P356: Enumeration of all $t$-ary trees with $n$ vertices
Input: Integers $t$ and $n$.
Output: All $t$-ary trees with $n$ vertices.
Complexity:
Comment:
Reference: [Er1987]
P357: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity: $O(1)$ time per solution.
Comment:
Reference: [Lucas1987]
P360: Enumeration of all trees with $n$ vertices and $m$ leaves
Input: Integers $n$ and $m$.
Output: All trees with $n$ vertices and $m$ leaves
Complexity:
Comment: I'm looking for this paper.
Reference: [Pallo1987]
P354: Enumeration of all $t$-ary trees in A-order
Input: Integers $t$ and $n$.
Output: All $t$-ary trees with $n$ vertices in A-order.
Complexity: $O(1)$ amortized time per solution.
Comment:
Reference: [VanBaronaigien1988]
P352: Enumeration of all binary trees with $n$ leaves
Input: An integer $n$.
Output: All binary trees with $n$ leaves.
Complexity: $O(1)$ amortized time per solution.
Comment: A strong Gray code can be listed in constant average time per solution.
Reference: [Ruskey1990]
P351: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity: $O(1)$ time per solution.
Comment: A loopless generation algorithm is an algorithm where the amount of computation to go from one object to the next is $O(1)$.
Reference: [VanBaronaigien1991]
P345: Enumeration of all $k$-ary trees in natural order
Input: Two integers $k$ and $n$.
Output: All $k$-ary trees with $n$ vertices.
Complexity:
Comment:
Reference: [Er1992]
P343: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity: $O(1)$ delay.
Comment:
Reference: [Lucas1993]
P334: Enumeration of all binary trees with $n$ vertices
Input: An integer $n$.
Output: All binary trees with $n$ vertices.
Complexity:
Comment:
Reference: [Bapiraju1994]
P337: Enumeration of all $k$-ary tree
Input: An integer $k$.
Output: All $k$-ary trees.
Complexity: $O(1)$ delay.
Comment:
Reference: [Korsh1994]
P319: Enumeration of all binary trees
Input:
Output: All binary trees.
Complexity: $O(1)$ time per tree.
Comment:
Reference: [Xiang1997]
P313: Enumeration of all $k$-ary trees with $n$ vertices
Input: Two integers $k$ and $n$.
Output: All $k$-ary trees with $n$ vertices.
Complexity: $O(1)$ delay.
Comment: Shifts and loopless algorithm.
Reference: [Korsh1998]
P149: Enumeration of all rooted plane trees with at most $n$ vertices
Input: An integer $n$.
Output: All rooted plane trees with at most $n$ vertices.
Complexity: $O(1)$ time per tree with $O(n)$ space.
Comment: A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.
Reference: [Nakano2002]
P150: Enumeration of all rooted plane trees with exactly $n$ vertices
Input: An integer $n$.
Output: All rooted plane trees with exactly $n$ vertices.
Complexity: $O(1)$ time per tree with $O(n)$ space.
Comment: A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.
Reference: [Nakano2002]
P151: Enumeration of all rooted plane trees with at most $n$ vertices and the maximum degree $D$
Input: Integers $n$ and $D$.
Output: All rooted plane trees with at most $n$ vertices and the maximum degree $D$.
Complexity: $O(1)$ time per tree with $O(n)$ space.
Comment: A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.
Reference: [Nakano2002]
P152: Enumeration of all rooted plane trees with exactly $n$ vertices and exactly $c$ leaves
Input: An integer $n$.
Output: All rooted plane trees with exactly $n$ vertices and exactly $c$ leaves .
Complexity: $O(n-c)$ time per tree with $O(n)$ space.
Comment: A \textit{rooted plane tree} is a rooted tree with a left-to-right ordering specified for the children of each vertex.
Reference: [Nakano2002]
P153: Enumeration of all plane trees with exactly $n$ vertices
Input: An integer $n$.
Output: All plane trees with exactly $n$ vertices.
Complexity: $O(n^3)$ time per tree with $O(n)$ space.
Comment: A \textit{plane tree} is a tree with a left-to-right ordering specified for the children of each vertex.
Reference: [Nakano2002]
P154: Enumeration of all rooted trees with at most $n$ vertices
Input: An integer $n$.
Output: All rooted tree with at most $n$ vertices.
Complexity: $O(1)$ time per tree and $O(n)$ space.
Comment: I'm looking for this paper.
Reference: [Nakano2003]
P290: Enumeration of all $n$-trees
Input: An integer $n$.
Output: All $n$-trees.
Complexity: $O(n^4N)$ total time.
Comment: Reverse search. $N$ is the number of solutions.
Reference: [Aringhieri2003]
P148: Enumeration of all trees with $n$ vertices and $d$ diameter
Input: Integers $n$ and $d$.
Output: All trees with $n$ vertices and $d$ diameter.
Complexity: $O(1)$ time per tree with $O(n)$ space.
Comment: By using the algorithm for each $d = 2, \dots, n-1$, all trees can be enumerated.
Reference: [Nakano2004]
P158: Enumeration of all $c$-tree with at most $v$ vertices and diameter $d$
Input: Integers $n$ and $d$
Output: All $c$-tree with at most $v$ vertices and diameter $d$.
Complexity: $O(1)$ time per tree.
Comment: A tree is a $c$-tree if each vertex has a color $c \in \{c_1, \dots, c_m\}$.
Reference: [Nakano2005a]
P276: Enumeration of all nonisomorphic rooted plane trees with $n$ vertices
Input: An integer $n$.
Output: All nonisomorphic rooted plane trees with $n$ vertices.
Complexity: Constant amortized time per solution.
Comment:
P277: Enumeration of all nonisomorphic free plane trees with $n$ vertices
Input: An integer $n$.
Output: All nonisomorphic free plane trees with $n$ vertices.
Complexity: Constant amortized time per solution.
Comment:
P242: Enumeration of all multitrees satisfying given constraints
Input: A set $\Sigma$ of labels, a function $val: \Sigma \to \mathbb{Z}^+$, and a feature vector $g$ of level $K$.
Output: All $(\Sigma, val)$-labeled multitrees $T$ such that $f_K(T) = g$ and $deg(v;T) = val(\ell(v))$ for all vertices $v \in T$.
Complexity:
Comment: This algorithm is for chemical graphs.
Reference: [Ishida2008]
P163: Enumeration of all ordered trees with $n$ vertices and $k$ leaves
Input: Integers $n$ and $k$.
Output: All ordered trees with $n$ vertices and $k$ leaves.
Complexity: $O(1)$ delay and $O(n)$ space.
Comment:
Reference: [Yamanaka2009a]
P166: Enumeration of all trees with specified degree sequence
Input: A degree sequence $D$.
Output: All trees with $D$.
Complexity: $O(1)$ time per tree.
Comment: I'm looking for this paper.
Reference: [Nakano2009]

#### Triangle

P396: Enumeration of all minimal triangle graphs with a fixed number vertices
Input: An integer $n$.
Output: All minimal triangle graphs with $n$ vertices.
Complexity:
Comment:
Reference: [Bowen1967b]
P182: Enumeration of all triangles in a graph
Input: A graph $G = (V, E)$.
Output: All triangles in $G$.
Complexity: $O(\alpha(G)|E|)$ total time and linear space.
Comment: $\alpha(G)$ is the minimum number of edge-disjoint spanning forests into which $G$ can be decomposed. If $G$ is planar, then the time complexity becomes $O(|V|)$. I'm looking for this paper.
Reference: [Chiba1985]

#### Triangulation

P395: Enumeration of all triangulations of 2-sphere
Input: A 2-sphere $G$.
Output: All triangulations of $G$.
Complexity:
Comment:
Reference: [Bowen1967a]
P321: Enumeration of all $r$-rooted $2$-connected triangulations of a planar graph
Input: A planar graph $G = (V, E)$ and an integer $r$.
Output: All $r$-rooted $2$-connected triangulations of $G$.
Complexity: $O(|V|^2N)$ total time and $O(|V|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Avis1996b]
P322: Enumeration of all $r$-rooted $3$-connected triangulations of a planar graph
Input: A planar graph $G = (V, E)$ and an integer $r$.
Output: All $r$-rooted $3$-connected triangulations of $G$.
Complexity: $O(|V|^2N)$ total time and $O(|V|)$ space.
Comment: $N$ is the number of solutions.
Reference: [Avis1996b]
P144: Enumeration of all based plane triangulations with $n$ vertices
Input: An integer $n$.
Output: All based plane triangulations.
Complexity: $O(1)$ time per based plane triangulation with $O(n)$ space.
Comment: A \textit{based plane triangulation} is a plane triangulation with one designated edge on the outer face. The algorithm does not output entire solution but output the difference from the previous solution.
Reference: [Nakano2004a]
P145: Enumeration of all biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face
Input: Integers $n$ and $r$.
Output: All biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face.
Complexity: $O(1)$ time per based plane triangulation with $O(n)$ space.
Comment: A \textit{based plane triangulation} is a plane triangulation with one designated edge on the outer face. The algorithm does not output entire solution but output the difference from the previous solution.
Reference: [Nakano2004a]
P146: Enumeration of all biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer face
Input: Integers $n$ and $r$.
Output: All biconnected based plane triangulations with $n$ vertices and $r$ vertices on the outer face.
Complexity: $O(r^2n)$ time per based plane triangulation with $O(n)$ space.
Comment:
Reference: [Nakano2004a]
P160: Enumeration of all rooted triconnected plane triangulations with at most $n$ vertices
Input: An integer $n$.
Output: All triconnected rooted plane triangulations with at most $n$ vertices.
Complexity: $O(1)$ time per tree and $O(n)$ space.
Comment: A \textit{rooted} plane triangulation is a plane triangulation with one designated vertex on the outer face.
Reference: [Nakano2001]
P161: Enumeration of all rooted triconnected plane triangulations with exactly $n$ vertices and $r$ leaves
Input: An integer $n$.
Output: All triconnected rooted plane triangulations with exactly $n$ vertices and $r$ leaves.
Complexity: $O(r)$ time per tree and $O(n)$ space.
Comment: A \textit{rooted} plane triangulation is a plane triangulation with one designated vertex on the outer face.
Reference: [Nakano2001]
P162: Enumeration of all triconnected plane triangulations with exactly $n$ vertices and $r$ leaves
Input: An integer $n$.
Output: All triconnected plane triangulations with exactly $n$ vertices and $r$ leaves.
Complexity: $O(r^n)$ time per triangulation and $O(n)$ space.
Comment:
Reference: [Nakano2001]
P19: Enumeration of all triangulations
Input: A set $S$ of $n$ points in the general position in the plane.
Output: all the triangulations whose vertex set is $S$ and edge set includes the convex hull of $S$.
Complexity: $O(\log\log n)$ time per triangulation and linear space.
Comment: Whether there is the algorithm that outputs all triangulations in constant time delay?
Reference: [Bespamyatnikh2002]
P170: Enumeration of all biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer faces
Input: Integers $n$ and $r$.
Output: All biconnected plane triangulations with $n$ vertices and $r$ vertices on the outer faces.
Complexity: $O(rn)$ time per triangulation and $O(n)$ space.
Comment:
Reference: [Nakano2004b]
P173: Enumeration of all triangulations of a triconnected plane graph of $n$ vertices
Input: A triconnected planar graph $G$ with $n$ vertices.
Output: All triangulations of $G$.
Complexity: $O(1)$ time per triangulation and $O(n)$ space.
Comment:
Reference: [Parvez2009]

#### Vertex cover

P264: Enumeration of all minimal vertex covers in a graph
Input: A graph $G = (V, E)$.
Output: All minimal vertex covers of size up to $k$ in $G$.
Complexity: $O^*(1.6181^k)$ total time.
Comment: This algorithm also lists some non-minimal vertex covers. This algorithm uses compact representation technique.
Reference: [Fernau2006]
P267: Enumeration of all minimal vertex covers of size at most $k$ in a graph
Input: A graph $G = (V, E)$.
Output: All minimal vertex covers of size at most $k$ in $G$.
Complexity: $O(|E| + k^2 2^k)$ total time.
Comment:
Reference: [Damaschke2006]

### Hypergraph

#### Acyclic subhypergraph

P40: Enumeration of all maximal $\alpha$-acyclic subhypergraphs in a hypergraph
Input: A hypergraph $H = (V, \mathcal{E})$.
Output: All maximal $\alpha$-acyclic subhypergraphs in $H$.
Complexity: $O(|\mathcal{E}|^2(|V|+|\mathcal{E}|))$ delay and $O(|\mathcal{E}|)$space.
Comment: The name of their algorithm is $\mathtt{GenMAS}$. This algorithm uses the algorithm $\mathtt{FindMAS}$ that outputs a maximal $\alpha$-acyclic subhypergraph.
Reference: [Daigo2009]
P176: Enumeration of all Berge acyclic subhypergraphs in a hypergraph
Input: A hypergraph $\mathcal{H}$.
Output: All Berge acyclic subhypergraphs in $\mathcal{H}$.
Complexity: $O(rd\tau(m))$ time per subhypergraph.
Comment: $r$ and $d$ are the rank and the degree of $\mathcal{H}$ and $\tau(m) = O((\log\log m)^2 / \log \log \log (m))$.
Reference: [Wasa2013]

#### Independent set

P300: Enumeration of all maximal independent set of a hypergraph of bounded dimension
Input: A hypergraph $H$ of bounded dimension.
Output: All maximal independent set of a hypergraph of bounded dimension.
Complexity:
Comment: The proposed algorithm runs in parallel.
Reference: [Boros2000a]
P139: Enumeration of all maximal independent sets in a $c$-conformal hypergraph
Input: A $c$-conformal hypergraph $\mathcal{H} \in A(k, r)$, where $c \le$ constant and $k + r \le c$.
Output: All maximal independent sets in $\mathcal{H}$.
Complexity: Incremental polynomial time.
Comment: $A(k, r)$ is the class of hyperedges with $(k, r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$.
Reference: [Boros2004]
P140: Enumeration of all maximal independent sets in a hypergraph of bounded intersections
Input: A hypergraph $\mathcal{H} \in A(k, r)$, where $k + r \le$ constant.
Output: All maximal independent sets in $\mathcal{H}$.
Complexity: Incremental polynomial time with polynomial space.
Comment: $A(k, r)$ is the class of hyperedges with $(k, r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$.
Reference: [Boros2004]

#### Transversal

P303: Enumeration of all minimal transversal of a hypergraph
Input: A hypergraph $\mathcal{H}$.
Output: All minimal transversal of $\mathcal{H}$.
Complexity: $(n + N)^{O(\log n)}$ total time with $O(n \log n)$ words.
Comment: $n = \sum_{X \in \mathcal{H}}|X|$ and $N$ is the number of solutions.
Reference: [Tamaki2000]
P141: Enumeration of all minimal transversal in a hypergraph
Input: A hypergraph $\mathcal{H}\in A(k, r)$.
Output: All minimal transversal in $\mathcal{H}$.
Complexity: $O(n^{k+r+1}|\mathcal{H}^d|^{r+1})$ total time and $O(N^{r+1})$ total space.
Comment: $A(k, r)$ is the class of hyperedges with $(k, r)$-bounded intersections, i.e. in which the intersection of any $k$ distinct hyperedges has size at most $r$. Minimal transversals of hypergraphs in some restricted classes can be enumerating in polynomial delay and space.
Reference: [Boros2004]

### Matroid

#### Basis

P65: Enumeration of all common bases in two matroids
Input: Two matroids $M_1 = (E, \beta_1)$ and $M_2 = (E, \beta_2)$.
Output: All $B \in \beta_1 \cap \beta_2$.
Complexity: $O(|E| ( |E|^2 + t)\lambda)$ total time and $O(|E|^2)$ space.
Comment: $\lambda$ is the number of common bases and $t$ is time complexity of one pivot operation.
Reference: [Fukuda1995]
P327: Enumeration of all basis of a matroid
Input: A matroid $M$ on the ground set $P$ with rank $m$.
Output: All basis of $M$.
Complexity: $O((m|P| + t(Piv))N)$ total time and space complexity independent of $N$.
Comment: $N$ is the number of solutions. $t(Piv)$ is the time necessary to do one pivot operation.
Reference: [Avis1996]

#### Spanning

P130: Enumeration of all minimal spanning and connected subsets in a matroid
Input: A matroid $M$.
Output: All minimal spanning and connected subsets in $M$.
Complexity: Incremental quasi-polynomial time.
Comment: $f(x)$ is a quasi-polynomial if $f(x) \in O(2^{polylog (n)})$.
Reference: [Khachiyan2006a]

#### Subset

P137: Enumeration of all maximal subset
Input: A binary matroid $M$ on ground set $S$ and $B = \{b_1, b_2\} \subseteq S$.
Output: All maximal subsets $X$ of $A := S \setminus B$ that span neither $b_1$ nor $b_2$.
Complexity: Incremental polynomial time.
Comment:
Reference: [Khachiyan2008a]

### Order

#### Ideal

P198: Enumeration of all $k$-cardinarity ideals of a $w$-element poset
Input: An integer $k$ and a poset $P$ with $w$ element, where $k \le w$.
Output: All $k$-cardinarity ideals of $P$.
Complexity: $O(Nw^3)$ total time.
Comment: $N$ is the number of ideals.
Reference: [Wild2013]

### Other

#### Assignment

P90: Enumeration of all assignment
Input: An integer $n$ and $n \times n$ cost matrix $C = (c_{ij})$.
Output: All assignments that minimizes $\sum^{i=n}_{i=1}\sum^{j=n}_{j=1} c_{ij}x_{ij}$ subject to $\sum^{i=n}_{i=1} x_{ij} = 1 \; (j = 1, \dots, n)$, $\sum^{j=n}_{j=1} x_{ij} = 1\; (i = 1, \dots, n)$, and $x_{ij} \ge 0$.
Complexity:
Comment:
Reference: [Murty1968]

#### Full disjunction

P266: Enumeration of all full disjunction in an acyclic set
Input: An acyclic set of relation $R$ with $N$ tuples.
Output: All full disjunctions of $R$.
Complexity: $O(N)$ delay.
Comment:
Reference: [Cohen2006]

#### Matrix

P269: Enumeration of all minimal sets of at most $k$ rows the deletion of which leaves a PP matrix
Input: A binary $n \times m$ matrix $B$ and a positive integer $k$, where $n > 4k$.
Output: All minimal sets of at most $k$ rows the deletion of which leaves a PP matrix.
Complexity: $O(3^k nm)$ time.
Comment: A PP matrix is a perfect phylogeny matrix.
Reference: [Damaschke2006]

#### Round-robin tournament score

P409: Enumeration of all round-robin tournament scores of $n$ players
Input: An integer $n$.
Output: All round-robin tournament scores of $n$ players.
Complexity:
Comment:
Reference: [Narayana1971]

### Permutation

#### Arrangements

P382: Enumeration of all arrangements with $n$ marks
Input: An integer $n$.
Output: All arrangements with $n$ marks.
Complexity: $O(n!)$ total time.
Comment:
Reference: [Wells1961]
P383: Enumeration of all arrangements with $n$ marks
Input: An integer $n$.
Output: All arrangements with $n$ marks.
Complexity: $O(n!)$ total time.
Comment:
Reference: [Johnson1963]

P44: Enumeration of all optimal ladder lotteries
Input: A permutation.
Output: All optimal ladder lotteries with satisfying the permutation.
Complexity: $O(1)$ time per solution on average, $O(n^2)$ space, and $O(n^2)$ time preprocessing.
Comment: $n$ is the length of the input permutation. We call a ladder lottery is an optimal when the number of horizontal lines in the ladder lottery is minimum. Ladder lotteries are also known as arrangements of pseudolines.
Reference: [Yamanaka2010]
P169: Enumeration of all ladder lotteries with $k$ bars
Input: A permutation $\pi$ and integer $k$.
Output: All ladder lotteries of $\pi$ with $k$ bars.
Complexity: $O(1)$ time per ladder lottery.
Comment: Ladder lotteries are also known as \textit{Amida kuji} in Japan. I'm looking for this paper.
Reference: [Yamanaka2014]

#### Set

P406: Enumeration of all permutations of a set of elements
Input: A set $S$.
Output: All permutations of $S$
Complexity:
Comment: He proposed the general algorithm for some combinatorial problems.
Reference: [Ehrlich1973a]
P405: Enumeration of all permutations of a set of elements
Input: A set $S$.
Output: All permutations of $S$
Complexity:
Comment:
Reference: [Dershowitz1975]

### SAT

#### Boolean CSP

P205: Enumeration of all models of $\phi$ by non-decreasing weight
Input: A $\Gamma$-formula $\phi$.
Output: All models of $\phi$ by non-decreasing weight.
Complexity: If $\Gamma$ is Horn or width-2 affine, there exists a polynomial delay algorithm.
Comment: Otherwise, such an algorithm does not exist unless $P \neq NP$.
Reference: [Creignou2011]

### Set

#### Bitstring

P355: Enumeration of all bitstrings of length $n$ that contains exactly $k$ 1's
Input: An even integer $n$ and odd integer $k$.
Output: All bitstrings of length $n$ that contains exactly $k$ 1's.
Complexity: $O(1)$ amortized time per solution.
Comment:
Reference: [Ruskey1988]

#### Ideals

P342: Enumeration of all ideals in a poset
Input: A poset $\mathcal{P}$.
Output: All ideals in $\mathcal{p}$.
Complexity: $O(1)$ delay.
Comment:
Reference: [Koda1993]

#### Partition

P411: Enumeration of all paritions in natural order
Input: An integer $n$.
Output: All partitions of $n$ in natural order
Complexity:
Comment:
Reference: [McKay1970]
P412: Enumeration of all paritions with restriction
Input: Integers $k$ and $n$.
Output: All partitions of $n$ whose the smallest part is greater than or equal to $k$.
Complexity:
Comment:
Reference: [White1970]
P408: Enumeration of all $k$-partitions of $n$
Input: Integers $k$ and $n$.
Output: All $k$-partitions of $n$.
Complexity:
Comment:
Reference: [Narayana1971]
P397: Enumeration of all paritions of an integer
Input: An integer $n$.
Output: All paritions of $n$.
Complexity:
Comment:
Reference: [Fenner1980]
P370: Enumeration of all partitions of a set
Input: A set $S$.
Output: All partitions of $S$.
Complexity: $O(1)$ amortized time per solution.
Comment:
Reference: [Semba1984]
P353: Enumeration of all partions of $n$ into integers of size at most $k$
Input: Integers $n$ and $k$.
Output: All partions of $n$ into integers of size at most $k$.
Complexity:
Comment:
Reference: [Savage1989]
P344: Enumeration of all partitions of a set into a fixed number of blocks
Input: An integer $k$.
Output: All partitions of a set into $k$ blocks
Complexity: $O(1)$ amortized time per solution.
Comment:
Reference: [Ruskey1993]
P332: Enumeration of all partitions of an integer $n$
Input: Three integers $n$, $k$, and $\sigma$.
Output: All partitions $P_\sigma(n, k)$ of $n$ into parts of size at most $k$ in which parts are congruent to $1$ modulo $\sigma$.
Complexity: $O(N)$ total time. E.g., $P_3(11, 8) = P_3(11, 7) = \left\{ \{7, 4\}, \{7, 1, 1, 1, 1\}, \{4, 4, 1, 1, 1\}, \{4, 1, 1, 1, 1, 1, 1, 1\}, \{1, \dots, 1\}\right\}$.
Comment: $N$ is the number of partitions.
Reference: [Rasmussen1995]
P333: Enumeration of all partitions of an integer $n$
Input: Two integers $n$ and $k$.
Output: All partitions $D(n, k)$ of $n$ into distinct parts of size at most $k$.
Complexity: $O(N)$ total time. E.g., $D(10, 5) = \{\{5, 4, 1\}, \{5, 3, 2\}, \{4, 3, 2, 1\}\}$ and $D(11, 4) = \emptyset$.
Comment: $N$ is the number of partitions.
Reference: [Rasmussen1995]
P159: Enumeration of all partition of $\{1, \dots, n\}$ into $k$ non-empty subsets
Input: An integer $k$.
Output: All partition of $\{1, \dots, n\}$ into $k$ non-empty subsets.
Complexity: $O(1)$ time per solution.
Comment: The number of such partitions is known as the Stirling number of the second kind.
Reference: [Kawano2005]
P258: Enumeration of all integer partitions in (anti-)lexicographical order
Input: An integer $n$.
Output: All integer partitions of $n$.
Complexity: $O(1)$ time per solution on average.
Comment:
Reference: [Stojmenovic2007]

### String

#### Binary string

P388: Enumeration of all binary string with fixed number ones
Input: Two integers $n$ and $k$, where $n \ge k$.
Output: All binary string with length $n$ and $k$ ones.
Complexity: $O(1)$ time per binary string.
Comment:
Reference: [Bitner1976]

#### Bracelet

P43: Enumeration of all $k$-ary bracelets
Input: $n$: a length of a bracelet, $k$: a number of alphabet size.
Output: All $k$-ary bracelets.
Complexity: $O(1)$ amortized per output and $O(n)$ space.
Comment: A bracelet is the lexicographically smallest element of an equivalence class of $k$-ary strings under string rotation and reversal.

#### Lyndon word

P293: Enumeration of all $k$-ary Lyndon brackets of length $n$
Input: Two integers $k$ and $n$.
Output: All $k$-ary Lyndon brackets of length $n$.
Complexity: $O(n)$ time per solution.
Comment:

#### Necklace

P402: Enumeration of all $k$-color necklaces with $n$ beads
Input: Integers $k$ and $n$.
Output: All $k$-color necklaces with $n$ beads
Complexity:
Comment:
Reference: [Fredricksen1978a]
P361: Enumeration of all necklaces of length $n$ with two colors
Input: An integer $n$.
Output: All necklaces of length $n$ with two colors.
Complexity:
Comment:
Reference: [Fredricksen1986b]
P41: Enumeration of all $k$-ary necklaces
Input: $n$: a length of a necklace, $k$: a number of alphabet size.
Output: All $k$-ary necklaces with length $n$.
Complexity: $O(1)$ amortized per output and $O(n)$ space.
Comment: A $k$-ary necklace is an equivalence class of k-ary strings under rotation.
Reference: [Ruskey1992]
P329: Enumeration of all $n$-bit necklaces with fixed density $d$
Input: Two integer $n$ and $d$.
Output: All $n$-bit necklaces with fixed density $d$.
Complexity: $O(nN)$ total time and $O(n)$ space.
Comment: $N$ is the number of solutions. A density of a $n$-bit necklace $T$ is $d$ if $T$ has $d$ ones.
Reference: [Wang1996]
P42: Enumeration of all $k$-ary necklaces with fixed density
Input: $n$: a length of a necklace, $k$: a number of alphabet size, $d$: a number of nonzero characters.
Output: All $k$-ary necklaces with fixed density $d$.
Complexity: $O(1)$ amortized per output and $O(n)$ space.
Comment: The set of $3$-ary necklace with $2$-density and $4$-length is $N_3(4,2) = \{0011, 0012, 0021, 0022, 0101, 0102, 0202\}$.
Reference: [Ruskey1999]
P304: Enumeration of all strings of some family
Input:
Output:
Complexity: Constant amortized time per solution.
Comment: This algorithm can list not only all necklaces but also all strings in other some family with CAT.
Reference: [Cattell2000]
P294: Enumeration of all $k$-ary necklaces with fixed content of length $n$
Input: Two integer $k$ and $n$, and a content.
Output: All $k$-ary necklaces with fixed content of length $n$.
Complexity: Constant amortized time per solution.
Comment:

#### Parenthesis

P373: Enumeration of all well-formed parenthesis with length $2n$
Input: An integer $n$.
Output: All well-formed parenthesis with length $2n$ in lexicographical ordering.
Complexity:
Comment:
Reference: [Er1983]
P315: Enumeration of all well-formed parenthesis strings of size $n$
Input: An integer $n$.
Output: All well-formed parenthesis strings of size $n$.
Complexity: $O(1)$ delay with $O(n)$ space, or $O(n)$ delay with $O(1)$ space.
Comment:
Reference: [Walsh1998]

#### Substring

P310: Enumeration of all $k$-ary strings of length $n$ that have no substring equal to $f$
Input: A $k$-ary string $f$ with length $m$, and a positive integer $n$.
Output: All $k$-ary strings of length $n$ that have no substring equal to $f$.
Complexity: $O(1)$ time per string.
Comment:
Reference: [Ruskey2000a]
P311: Enumeration of all circular $k$-ary strings of length $n$ that have no substring equal to $f$
Input: A $k$-ary string $f$ with length $m$, and a positive integer $n$.
Output: All circular $k$-ary strings of length $n$ that have no substring equal to $f$.
Complexity: $O(1)$ time per string.
Comment:
Reference: [Ruskey2000a]
P312: Enumeration of all $k$-ary necklaces of length $n$ that have no substring equal to $f$
Input: A $k$-ary string $f$ with length $m$, and a positive integer $n$.
Output: All $k$-ary necklaces of length $n$ that have no substring equal to $f$.
Complexity: $O(1)$ time per string.
Comment: $f$ is an aperiodic necklace.
Reference: [Ruskey2000a]

### Survey

#### Enumeration

P339: Enumeration of $k$-best enumeration
Input:
Output:
Complexity:
Comment: This is the full version of the Springer Encyclopedia of Algorithms, 2014.
Reference: [Eppstein2014]

#### Graph

P400: Alglrotihms for enumeration of all cycles in a given graph
Input: A graph $G$.
Output: All cycles belonging to $G$.
Complexity:
Comment: 26 cycle enumeration algorithms are introduced.
Reference: [Mateti1976a]
P338: Enumeration of clique enumeration
Input:
Output:
Complexity:
Comment: In Sec.3.
Reference: [Pardalos1994]
P330: Enumeration of gray code algorithms
Input:
Output:
Complexity:
Comment:
Reference: [Savage1997]

#### Logic

P197:
Input:
Output:
Complexity:
Comment: The author of this paper investigate the class of databases with constant delay the answers to a query.
Reference: [Segoufin2013]

### ZZZ (working)

#### Geometry

P111:
Input:
Output:
Complexity:
Comment:
Reference: [Seidel1990]

#### Geometry, Polyhedron

P61: Enumeration of all face-defining of a plane
Input:
Output:
Complexity: $O(m l(m,n)f)$ total time and $O(p(m, n))$ space.
Comment: $f$ is the number of output, and $l(m, n)$ and $p(m, n)$ are time and space complexity needed to solve an LP with $n$ variables and $m$ constraints.
Reference: [Fukuda1997]
P62: Enumeration of all vertex-defining of a plane
Input:
Output:
Complexity: $O(m^2 T(m,n)f)$ total time and $O(S(m, n))$ space.
Comment: $f$ is the number of output, and $T(m, n)$ and $S(m, n)$ are time and space complexity needed to solve RVP.
Reference: [Fukuda1997]

#### Geometry, vertex enumeration

P142:
Input:
Output:
Complexity:
Comment:
Reference: [Bussieck1998]

#### Graph

P314:
Input:
Output:
Complexity:
Comment: They give a general framework for generating graphs without duplication.
Reference: [McKay1998]
P261:
Input:
Output:
Complexity:
Comment:
Reference: [Ramon2007]
P221: Enumeration of all canonical embeddings of rooted graphs
Input:
Output: All canonical embeddings of rooted graphs in a class $\mathcal{H}$ over $\mathcal{B}$.
Complexity: $O(T(n))$ time per solution and $O(S(n) + n)$ space.
Comment:
Reference: [Zhuang2010b]

#### Graph, Clique

P207: Enumeration of all maximal cliques in a massive network
Input: A graph $G$.
Output: All maximal cliques in $G$.
Complexity: See the paper.
Comment: This algorithm works in limited memory.
Reference: [Cheng2011]

#### Graph, dominating sets, Hypergraph, transversal

P143:
Input:
Output:
Complexity:
Comment:
Reference: [Kante2011]

#### Graph, Edge cover

P238: Enumeration of all minimal edge-covers of an intersecting $st$-family
Input: A graph $G$.
Output: All minimal edge-covers of an intersecting $st$-family.
Complexity: Polynomial delay.
Comment: This complexity also holds for directed graphs.
Reference: [Nutov2009]

#### Graph, Other

P231:
Input:
Output:
Complexity:
Comment:
Reference: [Ramon2009]
P239: SFCL
Input:
Output:
Complexity: Incremental polynomial time.
Comment:
Reference: [Nutov2009]

#### Logic

P223: Enumeration of MS query of a word
Input:
Output:
Complexity:
Comment:
Reference: [Courcelle2009c]
P195: Enumeration of all answers to first-order queries
Input: A database $\mathbf{D} \in \mathcal{C}$ and query $\phi$.
Output: All answers on $\mathbf{D}$.
Complexity: $O(1)$ delay after linear preprocessing time.
Comment:
Reference: [Kazana2013b]
P196: Enumeration of all Monadic Second Order queries on a tree
Input:
Output:
Complexity: $O(1)$ delay after linear preprocessing time.
Comment: I'm looking for this paper.
Reference: [Kazana2013d]

#### Logic, Query

P262:
Input:
Output:
Complexity:
Comment:
Reference: [Durand2007]
P259:
Input:
Output:
Complexity:
Comment:
Reference: [Bagan2007a]

#### Matroid

P288:
Input:
Output:
Complexity:
Comment: Theorem 5, 6.
Reference: [Boros2004a]

#### Monomial

P211: Enumeration of all monomials
Input: A polynomial $P$ with $n$ variables, $t$ monomials, and a total degree $D$.
Output: All monomials of $P$.
Complexity: $O(D^2n^2\log(n)(n+\log(1/\epsilon))))$ delay.
Comment:
Reference: [Strozecki2010a]
P212: Enumeration of all monomials
Input: A polynomial $P$ with $n$ variables, $t$ monomials, and a total degree $D$.
Output: All monomials of $P$.
Complexity: The delay between $i$th and $i+1$th outputted monomials is bounded by $O(iDn^2(n+\log(1/\epsilon)))$.
Comment:
Reference: [Strozecki2010a]

#### Other, Bioinformatics

P218: Enumeration o all perfect phylogeneis
Input:
Output:
Complexity:
Comment: Using ZDDs.
Reference: [Kiyomi2012]

#### Query

P206:
Input:
Output:
Complexity:
Comment:
Reference: [Durand2011]

#### Set, Partitions

P164: Enumeration of all partitions of an integer positive $n$
Input: An integer $n$.
Output: All partitions with some additional property.
Complexity: $O(1)$ time per partition.
Comment: What is the property? I'm looking for this paper.
Reference: [Yamanaka2007]

#### String

P317:
Input:
Output:
Complexity:
Comment:
Reference: [Proskurowski1998]

# Acknowledgements

I am deeply grateful to Komei Fukuda, Andrea Marino, Yasuko Matsui, Valia Mitsou, Shin-ichi Nakano, Ryuhei Uehara, and Katsuhisa Yamanaka for enumerating.

# Reference

[Acuna2012]
Acu\~{n}a, V., Birmel\'{e}, E., Cottret, L., Crescenzi, P., Jourdan, F., Lacroix, V., Marchetti-Spaccamela, A., Marino, A., Milreu, P. V., Sagot, M.-F., and Stougie, L. (2012) Telling Stories: Enumerating Maximal Directed Acyclic Graphs With a Constrained Set of Sources and Targets. Theoretical Computer Science 457(0):1-9. doi:10.1016/j.tcs.2012.07.023 (Problem 200)
[Aichholzer2007]
Aichholzer, O., Aurenhammer, F., Huemer, C., and Vogtenhuber, B. (2007) Gray Code Enumeration of Plane Straight-Line Graphs. Graphs and Combinatorics 23(5):467-479. doi:10.1007/s00373-007-0750-z (Problem 255, Problem 256, Problem 257)
[Akkoyunlu1973]
Akkoyunlu, E. A. (1973) The Enumeration of Maximal Cliques of Large Graphs. SIAM Journal on Computing 2(1):1-6. doi:10.1137/0202001 (Problem 33)
[Alon1997]
Alon, N, Yuster, R., and Zwick, U. (1997) Finding and counting given length cycles. Algorithmica 17(3):209-223. doi:10.1007/BF02523189 (Problem 318)
[Aringhieri2003]
Aringhieri, R., Hansen, P., and Malucelli, F. (2003) Chemical trees enumeration algorithms. 4OR 1(1):67-83. doi:10.1007/s10288-002-0008-9 (Problem 290)
[Avis1996]
Avis, D. and Fukuda, K. (1996) Reverse search for enumeration. Discrete Applied Mathematics 65(1-3):21-46. doi:10.1016/0166-218X(95)00026-N (Problem 323, Problem 324, Problem 325, Problem 326, Problem 327, Problem 328)
[Avis1996b]
Avis, D. (1996) Generating Rooted Triangulations Without Repetitions. Algorithmica 16(6):618-632. doi:10.1007/BF01944353 (Problem 321, Problem 322)
[Azevedo1993]
Azevedo, J.A., {Santos Costa}, M. E. O., {Silvestre Madeira}, J. J. E.R., and {Vieira Martins}, E. Q. (1993) An algorithm for the ranking of shortest paths. European Journal of Operational Research 69(1):97-106. doi:10.1016/0377-2217(93)90095-5 (Problem 56)
[Babic1993]
Babi\'{c}, D. and Graovac, A. (1993) Enumeration of acyclic walks in a graph. Discrete Applied Mathematics 45(2):117-123. doi:10.1016/0166-218X(93)90055-S (Problem 45)
[Bagan2007a]
Bagan, G., Durand, A., and Grandjean, E. (2007) On Acyclic Conjunctive Queries and Constant Delay Enumeration. In: Duparc, J. and Henzinger, T. A. (eds.) CSL 2007: the 21st International Workshop on Computer Science Logic, Lausanne, Switzerland, Sep. 2007. Lecture Notes in Computer Science, vol 4646. Springer Berlin Heidelberg, p 208-222. doi:10.1007/978-3-540-74915-8_18 (Problem 259)
[Bapiraju1994]
Bapiraju, V. and Rao, V.V.B. (1994) Enumeration of binary trees. Information Processing Letters 51(3):125-127. doi:10.1016/0020-0190(94)00083-2 (Problem 334)
[Barbosa1999]
Barbosa, V. C. and Szwarcfiter, J. L. (1999) Generating all the acyclic orientations of an undirected graph. Information Processing Letters 72(1-2):71-74. doi:10.1016/S0020-0190(99)00120-9 (Problem 305)
[Basavaraju2014]
Basavaraju, M., Heggernes, P., {van ’t Hof}, P., Saei, R., and Villanger, Y. (2014) Maximal Induced Matchings in Triangle-Free Graphs. In: Kratsch, D. and Todinca, I. (eds.) WG 2014: the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, Nouan-le-Fuzelier, France, Jun. 2014. Lecture Notes in Computer Science, vol 8747. Springer International Publishing, p 93-104. doi:10.1007/978-3-319-12340-0_8 (Problem 424)
[Bauer2010a]
Bauer, R., Krug, M, and Wagner, D (2010) Enumerating and Generating Labeled k-degenerate Graphs. In: Sedgewick, R. and Golin, M. (eds.) ANALCO 2010: the 7th Workshop on Analytic Algorithmics and Combinatorics, Austin, Texas, USA, Jan. 2010. Society for Industrial and Applied Mathematics, p 90-98. doi:10.1137/1.9781611973006.12 (Problem 30, Problem 31)
[Beigel1999]
Beigel, R. (1999) Finding maximum independent sets in sparse and general graphs. In: Tarjan, R. E. and Warnow, T. (eds.) SODA 1999: the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Omni Inner Harbor Hotel, Baltimore, Maryland, USA, Jan. 1999. Society for Industrial and Applied Mathematics, p 856-857 (Problem 306, Problem 307, Problem 308, Problem 309)
[Bereg2005]
Bereg, S. (2005) Enumerating pseudo-triangulations in the plane. Computational Geometry 30(3):207-222. doi:10.1016/j.comgeo.2004.09.002 (Problem 279)
[Berry2000]
Berry, A., Bordat, J.-P., and Cogis, O. (2000) Generating All the Minimal Separators of a Graph. International Journal of Foundations of Computer Science 11(03):397-403. doi:10.1142/S0129054100000211 (Problem 302)
[Bespamyatnikh2002]
Bespamyatnikh, S. (2002) An efficient algorithm for enumeration of triangulations. Computational Geometry 23(3):271-279. doi:10.1016/S0925-7721(02)00111-6 (Problem 19)
[Beyer1980]
Beyer, T. and Hedetniemi, S. M. (1980) Constant Time Generation of Rooted Trees. SIAM Journal on Computing 9(4):706-712. doi:10.1137/0209055 (Problem 379)
[Birmele2012]
Birmel\'{e}, E, Crescenzi, P., and Ferreira, R. (2012) Efficient bubble enumeration in directed graphs. In: Calder\'{o}n-Benavides, L., Gonz\'{a}lez-Caro, C., Ch\'{a}vez, E., and Ziviani, N. (eds.) SPIRE 2012: the 19th International Symposium String Processing and Information Retrieval, Cartagena de Indias, Colombia, Oct. 2012. Lecture Notes in Computer Science, vol 7608. Springer Berlin Heidelberg, p 118-129. doi:10.1007/978-3-642-34109-0_13 (Problem 9)
[Bitner1976]
Bitner, J. R., Ehrlich, G., and Reingold, E. M. (1976) Efficient generation of the binary reflected gray code and its applications. Communications of the ACM 19(9):517-521. doi:10.1145/360336.360343 (Problem 388)
[Borassi2013]
Borassi, M., Crescenzi, P., Lacroix, V., Marino, A., Sagot, M.-F., and Milreu, P. V. (2013) Telling stories fast: Via linear-time delay pitch enumeration. In: Bonifaci, V., Demetrescu, C., and Marchetti-Spaccamela, A. (eds.) SEA 2013: the 12th International Symposium on Experimental Algorithms, Rome, Italy, Jun. 2013. Lecture Notes in Computer Science, vol 7933. Springer Berlin Heidelberg, p 200-211. doi:10.1007/978-3-642-38527-8_19 (Problem 16)
[Boros2000a]
Boros, E., Gurvich, V., Elbassioni, K., and Khachiyan, L. (2000) An Efficient Incremental Algorithm for Generating All Maximal Independent Sets in Hypergraphs of Bounded Dimension. Parallel Processing Letters 10(04):253-266. doi:10.1142/S0129626400000251 (Problem 300)
[Boros2004]
Boros, E. and Elbassioni, K. (2004) Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: Farach-Colton, M. (ed.) LATIN 2004: the 6th Latin American Symposium on Theoretical Informatics, Aires, Argentina, Apr. 2004. Lecture Notes in Computer Science, vol 2976. Springer Berlin Heidelberg, p 488-498. doi:10.1007/978-3-540-24698-5_52 (Problem 139, Problem 140, Problem 141)
[Boros2004a]
Boros, E., Elbassioni, K., and Gurvich, V. (2004) Generating paths and cuts in multi-pole (di) graphs. In: Fiala, J.ř., Koubek, V., and Kratochv\'{\i}l, J. (eds.) MFCS 2004: the 29th International Symposium on Mathematical Foundations of Computer Science, Prague, Czech Republic, Aug. 2004. Lecture Notes in Computer Science, vol 3153. Springer Berlin Heidelberg, p 298-309. doi:10.1007/978-3-540-28629-5_21 (Problem 287, Problem 288)
[Boros2004b]
Boros, E, Elbassioni, K, Gurvich, V, and Khachiyan, L (2004) Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems. In: Bienstock, D. and Nemhauser, G. (eds.) ICCO 2004: the 10th International Conference on Integer Programming and Combinatorial Optimization, New York, NY, USA, Jun. 2004. Lecture Notes in Computer Science, vol 3064. Springer Berlin Heidelberg, p 152-162. doi:10.1007/978-3-540-25960-2_12 (Problem 129)
[Boros2006]
Boros, E., Elbassioni, K., and Gurvich, V. (2006) Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms. Journal of Graph Theory 53(3):209-232. doi:10.1002/jgt.20180 (Problem 132, Problem 133, Problem 134)
[Boros2007]
Boros, E., Borys, K., Elbassioni, K., Gurvich, V., Makino, K., and Rudolf, G. (2007) Generating Minimal k-Vertex Connected Spanning Subgraphs. In: Lin, G. (ed.) COCOON 2007: the 13th Annual International Conference on Computing and Combinatorics, Banff, Canada, Jul. 2007. Lecture Notes in Computer Science, vol 4598. Springer Berlin Heidelberg, p 222-231. doi:10.1007/978-3-540-73545-8_23 (Problem 138)
[Bowen1967a]
Bowen, R. and Fisk, S. (1967) Generations of triangulations of the sphere. Mathematics of Computation 21(98):250-250. doi:10.1090/S0025-5718-1967-0223277-3 (Problem 395)
[Bowen1967b]
Bowen, R. (1967) The generation of minimal triangle graphs. Mathematics of Computation 21(98):248-248. doi:10.1090/S0025-5718-1967-0223276-1 (Problem 396)
[Brinkmann2011]
Brinkmann, G., Goedgebeur, J., and McKay, BD (2011) Generation of cubic graphs. Discrete Mathematics & Theoretical Computer Science 13(2):69-80 (Problem 427)
[Bron1973]
Bron, C. and Kerbosch, J. (1973) Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM 16(9):575-577. doi:10.1145/362342.362367 (Problem 188)
[Bronnimann2006a]
Br\"{o}nnimann, H., Kettner, L., Pocchiola, M., and Snoeyink, J. (2006) Counting and Enumerating Pointed Pseudotriangulations With the Greedy Flip Algorithm. SIAM Journal on Computing 36(3):721-739. doi:10.1137/050631008 (Problem 265)
[Bulo2007]
Bulo, S., Torsello, A., and Pelillo, M. (2007) A continuous-based approach for partial clique enumeration. In: Escolano, F. and Vento, M. (eds.) GbRPR 2007: the 6th IAPR-TC-15 International Workshop on Graph-Based Representations in Pattern Recognition, Alicante, Spain, Jun. 2007. Lecture Notes in Computer Science, vol 4538. Springer Berlin Heidelberg, p 61-70. doi:10.1007/978-3-540-72903-7_6 (Problem 260)
[Bussieck1998]
Bussieck, M. R and L\"{u}bbecke, M. E (1998) The vertex set of a 1/2-polytope is strongly P-enumerable. Computational Geometry 11(2):103-109. doi:10.1016/S0925-7721(98)00021-2 (Problem 142)
[Canfield1995]
Canfield, E. R. and Williamson, S. G. (1995) A loop-free algorithm for generating the linear extensions of a poset. Order 12(1):57-75. doi:10.1007/BF01108590 (Problem 331)
[Cattell2000]
Cattell, K., Ruskey, F., Sawada, J., Serra, M., and Miers, C.R. (2000) Fast Algorithms to Generate Necklaces, Unlabeled Necklaces, and Irreducible Polynomials Over GF(2). Journal of Algorithms 37(2):267-282. doi:10.1006/jagm.2000.1108 (Problem 304)
[Chandran2001]
Chandran, LS (2001) A Linear Time Algorithm for Enumerating All the Minimum and Minimal Separators of a Chordal Graph. In: Wang, J. (ed.) COCOON 2001: the 7th Annual International Conference Computing and Combinatorics, Guilin, China, Aug. 2001. Lecture Notes in Computer Science, vol 2108. Springer Berlin Heidelberg, p 308-317. doi:10.1007/3-540-44679-6_34 (Problem 297)
[Chandran2003]
Chandran, L.S., Ibarra, L., Ruskey, F., and Sawada, J. (2003) Generating and Characterizing the Perfect Elimination Orderings of a Chordal Graph. Theoretical Computer Science 307(2):303-317. doi:10.1016/S0304-3975(03)00221-4 (Problem 291)
[Chang1994a]
Chang, Y.H., Wang, J.S., and Lee, R.C.T. (1994) Generating all maximal independent sets on trees in lexicographic order. Information Sciences 76(3-4):279-296. doi:10.1016/0020-0255(94)90013-2 (Problem 335)
[Chang2013]
Chang, L., Yu, J. X., and Qin, L. (2013) Fast Maximal Cliques Enumeration in Sparse Graphs. Algorithmica 66(1):173-186. doi:10.1007/s00453-012-9632-8 (Problem 34)
[Char1970]
Char, J.P. (1970) Master circuit matrix. Proceedings of the Institution of Electrical Engineers 117(8):1655. doi:10.1049/piee.1970.0292 (Problem 430)
[Chegireddy1987]
Chegireddy, C. R. and Hamacher, H. W. (1987) Algorithms for finding K-best perfect matchings. Discrete Applied Mathematics 18(2):155-165. doi:10.1016/0166-218X(87)90017-5 (Problem 57)
[Cheng2011]
Cheng, J., Ke, Y., Fu, A. W.-C., Yu, J. X., and Zhu, L. (2011) Finding maximal cliques in massive networks. ACM Transactions on Database Systems 36(4):1-34. doi:10.1145/2043652.2043654 (Problem 207)
[Cheng2012b]
Cheng, J., Zhu, L., Ke, Y., and Chu, S. (2012) Fast algorithms for maximal clique enumeration with limited memory. In: Yang, Q. (ed.) KDD 2012: the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, Beijing, China, Aug. 2012. ACM Press, p 1240. doi:10.1145/2339530.2339724 (Problem 201)
[Chiba1985]
Chiba, N. and Nishizeki, T. (1985) Arboricity and Subgraph Listing Algorithms. SIAM Journal on Computing 14(1):210-223. doi:10.1137/0214017 (Problem 182, Problem 183, Problem 184, Problem 185)
[Cohen2006]
Cohen, S., Fadida, I., Kanza, Y., Kimelfeld, B., and Sagiv, Y. (2006) Full disjunctions: polynomial-delay iterators in action. In: VLDB 2006: the 32nd international conference on Very Large Data Bases, COEX, Seoul, Korea, Sep. 2006. VLDB Endowment, p 739-750 (Problem 266)
[Cohen2008]
Cohen, S., Kimelfeld, B., and Sagiv, Y. (2008) Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. Journal of Computer and System Sciences 74(7):1147-1159. doi:10.1016/j.jcss.2008.04.003 (Problem 253)
[Courcelle2009c]
Courcelle, B. (2009) Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics 157(12):2675-2700. doi:10.1016/j.dam.2008.08.021 (Problem 223)
[Creignou2011]
Creignou, N., Olive, F., and Schmidt, J. (2011) Enumerating all solutions of a Boolean CSP by non-decreasing weight. In: Sakallah, K. A. and Simon, L. (eds.) SAT 2011: the 14th International Conference Theory and Applications of Satisfiability Testing, Ann Arbor, MI, USA,, Jun. 2011. Lecture Notes in Computer Science, vol 6695. Springer Berlin Heidelberg, p 120-133. doi:10.1007/978-3-642-21581-0_11 (Problem 205)
[Daigo2009]
Daigo, T. and Hirata, K. (2009) On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay. In: Nielsen, M., Ku\v{c}era, A., Miltersen, P. B., Palamidessi, C., Tůma, P., and Valencia, F. (eds.) SOFSEM 2009: the 35th Conference on Current Trends in Theory and Practice of Computer Science, \v{S}pindlerův Ml\'{y}n, Czech Republic, Jan. 2009. Lecture Notes in Computer Science, vol 5404. Springer Berlin Heidelberg, p 181-192. doi:10.1007/978-3-540-95891-8_19 (Problem 40)
[Damaschke2006]
Damaschke, P. (2006) Parameterized Enumeration, Transversals, and Imperfect Phylogeny Reconstruction. Theoretical Computer Science 351(3):337-350. doi:10.1016/j.tcs.2005.10.004 (Problem 267, Problem 268, Problem 269)
[Danielson1968]
Danielson, G. (1968) On finding the simple paths and circuits in a graph. IEEE Transactions on Circuit Theory 15(3):294-295. doi:10.1109/TCT.1968.1082837 (Problem 415, Problem 416)
[Dershowitz1975]
Dershowitz, N. (1975) A simplified loop-free algorithm for generating permutations. BIT 15(2):158-164. doi:10.1007/BF01932689 (Problem 405)
[Deza1993]
Deza, A., Fukuda, K, and Rosta, V. (1993) Wagner's theorem and combinatorial enumeration of 3-polytopes. Research reports on information sciences. Ser. B, Operations research 271:1-5 (Problem 340)
[Dias2005]
Dias, V. M.F., de Figueiredo, C. M.H., and Szwarcfiter, J. L. (2005) Generating Bicliques of a Graph in Lexicographic Order. Theoretical Computer Science 337(1-3):240-248. doi:10.1016/j.tcs.2005.01.014 (Problem 280)
[Dickerson1992]
Dickerson, M. T., Drysdale, R.L. S., and Sack, J.-R. (1992) Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors. International Journal of Computational Geometry \& Applications 02(03):221-239. doi:10.1142/S0218195992000147 (Problem 46)
Dourado, M. C., Oliveira, R. A., and Protti, F. (2014) Algorithmic Aspects of Steiner Convexity and Enumeration of Steiner Trees. Annals of Operations Research 223(1):155-171. doi:10.1007/s10479-014-1607-5 (Problem 263)
[Du2009]
Du, N., Wu, B., Xu, L., Wang, B., and Pei, X. (2006) A Parallel Algorithm for Enumerating All Maximal Cliques in Complex Network. In: ICDMW 2006: the 6th IEEE International Conference on Data Mining - Workshops, Hong Kong, China, Dec. 2006. IEEE, p 320-324. doi:10.1109/ICDMW.2006.17 (Problem 222)
[Dumitrescu2001]
Dumitrescu, A., G\"{a}rtner, B., Pedroni, S., and Welzl, E. (2001) Enumerating triangulation paths. Computational Geometry 20(1-2):3-12. doi:10.1016/S0925-7721(01)00031-1 (Problem 298)
[Durand2007]
Durand, A. and Grandjean, E. (2005) First-order queries on structures of bounded degree are computable with constant delay. ACM Transactions on Computational Logic 8(4):18. doi:10.1145/1276920.1276923 (Problem 262)
[Durand2011]
Durand, A. and Strozecki, Y. (2011) Enumeration Complexity of Logical Query Problems with Second-order Variables. In: Bezem, M. (ed.) CSL 2011: the 25th International Workshop/20th Annual Conference of the EACSL - Computer Science Logic, Dagstuhl, Germany, Aug. 2011. Leibniz International Proceedings in Informatics (LIPIcs), vol 12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, p 189-202. doi:10.4230/LIPIcs.CSL.2011.189 (Problem 206)
[Ehrenfeucht1973]
Ehrenfeucht, A., Fosdick, L. D., and Osterweil, L. J. (1973) An algorithm for finding the elementary circuits of a directed graph. Dept. of Computer Sci., Univ. of Colorado, Boulder, CU-CS-024-23. (Problem 431)
[Ehrlich1973a]
Ehrlich, G. (1973) Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations. Journal of the ACM 20(3):500-513. doi:10.1145/321765.321781 (Problem 406)
[Eppstein1992]
Eppstein, D. (1992) Finding the k smallest spanning trees. BIT 32(2):237-248. doi:10.1007/BF01994879 (Problem 47, Problem 48, Problem 49, Problem 50)
[Eppstein1997]
Eppstein, D., Galil, Z., Italiano, G. F., and Nissenzweig, A. (1997) Sparsification---A Technique for Speeding Up Dynamic Graph Algorithms. Journal of the ACM 44(5):669-696. doi:10.1145/265910.265914 (Problem 59, Problem 60)
[Eppstein1998]
Eppstein, D. (1998) Finding the K Shortest Paths. SIAM Journal on Computing 28(2):652-673. doi:10.1137/S0097539795290477 (Problem 58)
[Eppstein2003a]
Eppstein, D. (2003) Small Maximal Independent Sets and Faster Exact Graph Coloring. Journal of Graph Algorithms and Applications 7(2):131-140. doi:10.7155/jgaa.00064 (Problem 292)
[Eppstein2010]
Eppstein, D., L\"{o}ffler, M, and Strash, D. (2010) Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong, O., Chwa, K.-Y., and Park, K. (eds.) ISAAC 2010: the 21st International Symposium on Algorithms and Computation, Jeju Island, Korea, Dec. 2010. Lecture Notes in Computer Science, vol 6506. Springer Berlin Heidelberg, p 403-414. doi:10.1007/978-3-642-17517-6_36 (Problem 210)
[Eppstein2014]
Eppstein, D. (2014) $K$-Best Enumeration. Cornell University, arXiv ID: 1412.5075. (Problem 339)
[Er1983]
Er, M. C. (1983) A Note on Generating Well-Formed Parenthesis Strings Lexicographically. The Computer Journal 26(3):205-207. doi:10.1093/comjnl/26.3.205 (Problem 373)
[Er1985]
Er, M. C. (1985) Enumerating Ordered Trees Lexicographically. The Computer Journal 28(5):538-542. doi:10.1093/comjnl/28.5.538 (Problem 366)
[Er1987]
Er, M. C. (1987) Lexicographic Listing and Ranking of T-Ary Trees. The Computer Journal 30(6):569-572. doi:10.1093/comjnl/30.6.569 (Problem 356)
[Er1992]
Er, M. C. (1992) Efficient Generation of K-Ary Trees in Natural Order. The Computer Journal 35(3):306-308. doi:10.1093/comjnl/35.3.306 (Problem 345)
[Fenner1980]
Fenner, T. I. (1980) A binary tree representation and related algorithms for generating integer partitions. The Computer Journal 23(4):332-337. doi:10.1093/comjnl/23.4.332 (Problem 397)
[Fernau2006]
Fernau, H. (2006) Edge dominating set: Efficient enumeration-based exact algorithms. In: Bodlaender, H. L. and Langston, M. A. (eds.) IWPEC 2006: the 2nd International Workshop on Parameterized and Exact Computation, Z\"{u}rich, Switzerland, Sep. 2006. Lecture Notes in Computer Science, vol 4169. Springer Berlin Heidelberg, p 142-153. doi:10.1007/11847250_13 (Problem 264)
[Ferreira2011]
Ferreira, R., Grossi, R., and Rizzi, R. (2011) Output-sensitive listing of bounded-size trees in undirected graphs. In: Demetrescu, C. and Halld\'{o}rsson, M. M. (eds.) ESA 2011: the 19th Annual European Symposium on Algorithms, Saarbr\"{u}cken, Germany, Sep. 2011. Lecture Notes in Computer Science, vol 6942. Springer Berlin Heidelberg, p 275-286. doi:10.1007/978-3-642-23719-5_24 (Problem 2)
[Ferreira2012]
Birmel\'{e}, E., Ferreira, R., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., and Sacomoto, G. (2012) Optimal Listing of Cycles and st-Paths in Undirected Graphs. In: Khanna, S. (ed.) SODA 2012: the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, Jan. 2012. p 1884-1896. doi:10.1137/1.9781611973105.134 (Problem 5, Problem 10)
[Ferreira2014]
Ferreira, R., Grossi, R., Rizzi, R., Sacomoto, G., and Marie-France, S. (2014) Amortized \$\backslash tilda\{O\}(|V|)\$ -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs. In: Schulz, A. S. and Wagner, D. (eds.) ESA 2014: the 22th Annual European Symposium on Algorithms, Wroclaw, Poland, Sep. 2014. Lecture Notes in Computer Science, vol 8737. Springer Berlin Heidelberg, p 418-429. doi:10.1007/978-3-662-44777-2_35 (Problem 11, Problem 13)
[Florian1981]
Florian, M., Nguyen, S., and Pallottino, S. (1981) A dual simplex algorithm for finding all shortest paths. Networks 11(4):367-378. doi:10.1002/net.3230110406 (Problem 178)
[Fomin2008]
Fomin, F. V., Grandoni, F., Pyatkin, A. V., and Stepanov, A. A. (2008) Combinatorial bounds via measure and conquer. ACM Transactions on Algorithms 5(1):1-17. doi:10.1145/1435375.1435384 (Problem 240)
[Frederickson1985]
Frederickson, G. N. (1985) Data Structures for On-Line Updating of Minimum Spanning Trees, With Applications. SIAM Journal on Computing 14(4):781-798. doi:10.1137/0214055 (Problem 53, Problem 54)
[Fredricksen1978a]
Fredricksen, H. and Maiorana, J. (1978) Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Mathematics 23(3):207-210. doi:10.1016/0012-365X(78)90002-X (Problem 402)
[Fredricksen1986b]
Fredricksen, H. and {J. Kessler}, I. (1986) An algorithm for generating necklaces of beads in two colors. Discrete Mathematics 61(2-3):181-188. doi:10.1016/0012-365X(86)90089-0 (Problem 361)
[Fukuda1991]
Fukuda, K., Saito, S., and Tamura, A. (1991) Combinatorial face enumeration in arrangements and oriented matroids. Discrete Applied Mathematics 31(2):141-149. doi:10.1016/0166-218X(91)90066-6 (Problem 66)
[Fukuda1992]
Fukuda, K. and Matsui, T. (1992) Finding all minimum-cost perfect matchings in Bipartite graphs. Networks 22(5):461-468. doi:10.1002/net.3230220504 (Problem 63)
[Fukuda1994]
Fukuda, K. and Matsui, T. (1994) Finding All the Perfect Matchings in Bipartite Graphs. Applied Mathematics Letters 7(1):15-18. doi:10.1016/0893-9659(94)90045-0 (Problem 64)
[Fukuda1995]
Fukuda, K. and Namiki, M. (1995) Finding all common bases in two matroids. Discrete Applied Mathematics 56(2-3):231-243. doi:10.1016/0166-218X(94)00088-U (Problem 65)
[Fukuda1997]
Fukuda, K., Liebling, T. M., and Margot, F. (1997) Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Computational Geometry 8(1):1-12. doi:10.1016/0925-7721(95)00049-6 (Problem 61, Problem 62)
[Gabow1977]
Gabow, H. N. (1977) Two Algorithms for Generating Weighted Spanning Trees in Order. SIAM Journal on Computing 6(1):139-150. doi:10.1137/0206011 (Problem 51, Problem 52)
[Gabow1978]
Gabow, H. N. and Myers, E. W. (1978) Finding All Spanning Trees of Directed and Undirected Graphs. SIAM Journal on Computing 7(3):280-287. doi:10.1137/0207024 (Problem 67, Problem 68)
[Gabow1986a]
Gabow, H. N., Galil, Z., Spencer, T., and Tarjan, R. E. (1986) Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2):109-122. doi:10.1007/BF02579168 (Problem 362, Problem 363)
[Garey1978]
Garey, M. R. and Tarjan, R. E. (1978) A linear-time algorithm for finding all feedback vertices. Information Processing Letters 7(6):274-276. doi:10.1016/0020-0190(78)90015-7 (Problem 177)
[Gely2009]
G\'{e}ly, A., Nourine, L., and Sadi, B. (2009) Enumeration aspects of maximal cliques and bicliques. Discrete Applied Mathematics 157(7):1447-1459. doi:10.1016/j.dam.2008.10.010 (Problem 224, Problem 225, Problem 226)
[Gen-Huey1994]
Gen-Huey, C. and Yung-Chen, H. (1994) Algorithms for the Constrained Quickest Path Problem and the Enumeration of Quickest Paths. Computers \& Operations Research 21(2):113-118. doi:10.1016/0305-0548(94)90045-0 (Problem 336)
[Gerhards1979]
Gerhards, L. and Lindenberg, W. (1979) Clique detection for nondirected graphs: Two new algorithms. Computing 21(4):295-322. doi:10.1007/BF02248731 (Problem 387)
[Gilbert1958]
Gilbert, E. N. (1958) Gray Codes and Paths on the n-Cube. Bell System Technical Journal 37(3):815-826. doi:10.1002/j.1538-7305.1958.tb03887.x (Problem 428)
[Goldberg1993b]
Goldberg, L. A. (1993) Polynomial space polynomial delay algorithms for listing families of graphs. In: STOC 1993: the 25th annual ACM symposium on Theory of computing, San Diego, CA, USA, Jun. 1993. ACM Press, p 218-225. doi:10.1145/167088.167160 (Problem 341)
[Golovach2013a]
Golovach, PA and Heggernes, P. (2013) An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. In: Fomin, F. V., Freivalds, Rū.ņ., Kwiatkowska, M., and Peleg, D. (eds.) ICALP 2013: the 40th International Colloquium on Automata, Languages, and Programming, Riga, Latvia, Jul. 2013. Lecture Notes in Computer Science, vol 7965. Springer Berlin Heidelberg, p 485-496. doi:10.1007/978-3-642-39206-1_41 (Problem 124, Problem 125, Problem 126, Problem 127, Problem 128)
[Golovach2015]
Golovach, P. A., Heggernes, P., Kant\'{e}, M. M., Kratsch, D., and Villanger, Y. (2015) Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics --(--):-. doi:10.1016/j.dam.2014.12.010 (Problem 425)
[Gusfield1989]
Gusfield, D. and Irving, R. W. (1989) The Stable Marriage Problem: Structure and Algorithms. MIT Press (Problem 69)
[Hakimi1961]
Hakimi, S.L. (1961) On trees of a graph and their generation. Journal of the Franklin Institute 272(5):347-359. doi:10.1016/0016-0032(61)90036-9 (Problem 392)
[Hakimi1964]
Hakimi, S. and Green, D. (1964) Generation and Realization of Trees and k-Trees. IEEE Transactions on Circuit Theory 11(2):247-255. doi:10.1109/TCT.1964.1082276 (Problem 432)
[Hamacher1984a]
Hamacher, H. W., Picard, J.-C., and Queyranne, M. (1984) On Finding the K Best Cuts in a Network. Operations Research Letters 2(6):303-305. doi:10.1016/0167-6377(84)90083-X (Problem 70, Problem 372)
[Hariharan1995]
Hariharan, R., Kapoor, S., and Kumar, V. (1995) Faster enumeration of all spanning trees of a directed graph. In: Akl, S. G., Dehne, F., Sack, J.-R., and Santoro, N. (eds.) WADS 1995: the 4th International Workshop on Algorithms and Data Structures, Kingston, Canada, Aug. 1995. Lecture Notes in Computer Science, vol 955. Springer Berlin Heidelberg, p 428-439. doi:10.1007/3-540-60220-8_82 (Problem 301)
[Henry2013]
Henry, CJ and Ramanna, S. (2013) Maximal clique enumeration in Finding Near Neighbourhoods. In: Peters, J. F., Skowron, A., Ramanna, S., Suraj, Z., and Wang, X. (eds.) Transactions on Rough Sets XVI, Banff, Canada, Oct. 2013. Lecture Notes in Computer Science, vol 7736. Springer Berlin Heidelberg, p 103-124. doi:10.1007/978-3-642-36505-8_7 (Problem 190)
[Hikita1983]
Hikita, T. (1983) Listing and counting subtrees of equal size of a binary tree. Information Processing Letters 17(4):225-229. doi:10.1016/0020-0190(83)90046-7 (Problem 374)
[Hoang2013]
Ho\`{a}ng, C. T., Kamiński, M., Sawada, J., and Sritharan, R. (2013) Finding and listing induced paths and cycles. Discrete Applied Mathematics 161(4-5):633-641. doi:10.1016/j.dam.2012.01.024 (Problem 192, Problem 193, Problem 194)
[Huffner2009]
H\"{u}ffner, F., Komusiewicz, C., Moser, H., and Niedermeier, R. (2009) Isolation Concepts for Clique Enumeration: Comparison and Computational Experiments. Theoretical Computer Science 410(52):5384-5397. doi:10.1016/j.tcs.2009.05.008 (Problem 232, Problem 233)
[Ishida2008]
Ishida, Y., Zhao, L., Nagamochi, H., and Akutsu, T. (2008) Improved Algorithms for Enumerating Tree-like Chemical Graphs with Given Path Frequency. In: Arthur, J. and Ng, S.-K. (eds.) the 19th International Conference on Genome Informatics 2008, Gold Coast, Queensland, Australia, Dec. 2008. Genome Informatics Series, vol 21. Imperial College Press, p 53-64. doi:10.1142/9781848163324_0005 (Problem 242)
[Ito2005]
Ito, H., Iwama, K., and Osumi, T. (2005) Linear-time enumeration of isolated cliques. In: Brodal, G. S. and Leonardi, S. (eds.) ESA 2005: the 13th Annual European Symposium on Algorithms, Palma de Mallorca, Spain, Oct. 2005. Lecture Notes in Computer Science, vol 3669. Springer Berlin Heidelberg, p 119-130. doi:10.1007/11561071_13 (Problem 281)
[Ito2009]
Ito, H. and Iwama, K. (2009) Enumeration of isolated cliques and pseudo-cliques. ACM Transactions on Algorithms 5(4):1-21. doi:10.1145/1597036.1597044 (Problem 229, Problem 230)
[Jayakumar1984]
Jayakumar, R., Thulasiraman, K., and Swamy, M. (1984) Complexity of computation of a spanning tree enumeration algorithm. IEEE Transactions on Circuits and Systems 31(10):853-860. doi:10.1109/TCS.1984.1085435 (Problem 371)
[Johnson1963]
Johnson, S. M. (1963) Generation of permutations by adjacent transposition. Mathematics of Computation 17(83):282-282. doi:10.1090/S0025-5718-1963-0159764-2 (Problem 383)
[Johnson1975]
Johnson, D. B. (1975) Finding All the Elementary Circuits of a Directed Graph. SIAM Journal on Computing 4(1):77-84. doi:10.1137/0204007 (Problem 7)
[Johnson1988]
Johnson, D. S., Yannakakis, M., and Papadimitriou, C. H. (1988) On generating all maximal independent sets. Information Processing Letters 27(3):119-123. doi:10.1016/0020-0190(88)90065-8 (Problem 29)
[Johnston1976]
Johnston, H. C. (1976) Cliques of a graph-variations on the Bron-Kerbosch algorithm. International Journal of Computer \& Information Sciences 5(3):209-238. doi:10.1007/BF00991836 (Problem 404)
[Kamae1967]
Kamae, T. (1967) A Systematic Method of Finding All Directed Circuits and Enumerating All DIrected Paths. IEEE Transactions on Circuit Theory 14(2):166-171. doi:10.1109/TCT.1967.1082699 (Problem 420, Problem 421)
[Kanevsky1993]
Kanevsky, A. (1993) Finding all minimum-size separating vertex sets in a graph. Networks 23(6):533-541. doi:10.1002/net.3230230604 (Problem 71)
[Kante2011]
Kant\'{e}, MM, Limouzy, V., Mary, A., and Nourine, L (2011) Enumeration of minimal dominating sets and variants. In: Owe, O., Steffen, M., and Telle, J. A. (eds.) FCT 2011: the 18th International Symposium on Fundamentals of Computation Theory, Oslo, Norway, Aug. 2011. Lecture Notes in Computer Science, vol 6914. Springer Berlin Heidelberg, p 298-309. doi:10.1007/978-3-642-22953-4_26 (Problem 143)
[Kante2012]
Kant\'{e}, MM, Limouzy, V., Mary, A., and Nourine, L (2012) On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets. In: Chao, K.-M., Hsu, T., and Lee, D.-T. (eds.) ISAAC 2012: the 23rd International Symposium on Algorithms and Computation, Taipei, Taiwan, Dec. 2012. Lecture Notes in Computer Science, vol 7676. Springer Berlin Heidelberg, p 289-298. doi:10.1007/978-3-642-35261-4_32 (Problem 202, Problem 203, Problem 204)
[Kante2013]
Kant\'{e}, M.M. MM, Limouzy, V., Mary, A., Nourine, L., and Uno, T. (2013) On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs. In: Cai, L., Cheng, S.-W., and Lam, T.-W. (eds.) ISAAC 2013: the 24th International Symposium on Algorithms and Computation, Hong Kong, China, Dec. 2013. Lecture Notes in Computer Science, vol 8283. Springer Berlin Heidelberg, p 339-349. doi:10.1007/978-3-642-45030-3_32 (Problem 35, Problem 36)
[Kante2014]
Kant\'{e}, M. M., Limouzy, V., Mary, A., and Nourine, L. (2014) On the Enumeration of Minimal Dominating Sets and Related Notions. SIAM Journal on Discrete Mathematics 28(4):1916-1929. doi:10.1137/120862612 (Problem 348)
[Kapoor1991]
Kapoor, S. and Ramesh, H (1991) Algorithms for generating all spanning trees of undirected, directed and weighted graphs. In: Dehne, F., Sack, J.-R., and Santoro, N. (eds.) WADS 1991: the 2nd Workshop on Algorithms and Data Structures, Ottawa, Canada, Aug. 1991. Lecture Notes in Computer Science, vol 519. Springer Berlin Heidelberg, p 461-472. doi:10.1007/BFb0028284 (Problem 73, Problem 74, Problem 75)
[Kashiwabara1992]
Kashiwabara, T., Masuda, S., Nakajima, K., and Fujisawa, T. (1992) Generation of Maximum Independent Sets of a Bipartite Graph and Maximum Cliques of a Circular-Arc Graph. Journal of Algorithms 13(1):161-174. doi:10.1016/0196-6774(92)90012-2 (Problem 76, Problem 77, Problem 347)
[Katoh1981]
Katoh, N., Ibaraki, T., and Mine, H. (1981) Minimum Spanning Trees. SIAM Journal on Computing 10(2):247-255. doi:10.1137/0210017 (Problem 55)
[Katoh2009a]
Katoh, N. and Tanigawa, S. (2009) Fast enumeration algorithms for non-crossing geometric graphs. Discrete and Computational Geometry 42(3):443-468. doi:10.1007/s00454-009-9164-4 (Problem 248, Problem 249, Problem 250, Problem 251, Problem 252)
[Kawano2005]
Kawano, S. and Nakano, S. (2005) Constant time generation of set partitions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E88-A(4):930-934. doi:10.1093/ietfec/e88-a.4.930 (Problem 159, Problem 165)
[Kazana2013b]
Kazana, W. and Segoufin, L. (2013) Enumeration of first-order queries on classes of structures with bounded expansion. In: Hull, R. (ed.) PODS 2013: the 32nd symposium on Principles of database systems, New York, New York, USA, Jun. 2013. ACM Press, p 297. doi:10.1145/2463664.2463667 (Problem 195)
[Kazana2013d]
Kazana, W. and Segoufin, L. (2013) Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic 14(4):25:1-25:12. doi:10.1145/2528928 (Problem 196)
[Khachiyan2005]
Khachiyan, L, Boros, E, and Borys, K (2005) Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs. In: Deng, X. and Du, D.-Z. (eds.) ISAAC 2005: the 16th International Symposium on Algorithms and Computation, Sanya, Hainan, China, Dec. 2005. Lecture Notes in Computer Science, vol 3827. Springer Berlin Heidelberg, p 156-165. doi:10.1007/11602613_17 (Problem 282)
[Khachiyan2006a]
Khachiyan, L, Boros, E, and Borys, K (2006) Enumerating spanning and connected subsets in graphs and matroids. In: Azar, Y. and Erlebach, T. (eds.) ESA 2006: the 14th Annual European Symposium on Algorithms, Zurich, Switzerland, Sep. 2006. Lecture Notes in Computer Science, vol 4168. Springer Berlin Heidelberg, p 444-455. doi:10.1007/11841036_41 (Problem 130, Problem 131)
[Khachiyan2008a]
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V., and Makino, K. (2008) Generating cut conjunctions in graphs and related problems. Algorithmica 51(3):239-263. doi:10.1007/s00453-007-9111-9 (Problem 135, Problem 136, Problem 137)
[Kijima2010]
Kijima, S., Kiyomi, M., Okamoto, Y., and Uno, T. (2010) On Listing, Sampling, and Counting the Chordal Graphs With Edge Constraints. Theoretical Computer Science 411(26-28):2591-2601. doi:10.1016/j.tcs.2010.03.024 (Problem 213)
[Kiyomi2006]
Kiyomi, M. and Takeaki, U. (2006) Generating Chordal Graphs Included in Given Graphs. IEICE Transactions on Information and Systems E89-D(2):763-770. doi:10.1093/ietisy/e89-d.2.763 (Problem 270, Problem 271)
[Kiyomi2006a]
Kiyomi, M., Kijima, S., and Uno, T. (2006) Listing chordal graphs and interval graphs. In: Fomin, F. V. (ed.) WG 2006: the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, Bergen, Norway, Jun. 2006. Lecture Notes in Computer Science, vol 4271. Springer Berlin Heidelberg, p 68-77. doi:10.1007/11917496_7 (Problem 272, Problem 273, Problem 274)
[Kiyomi2012]
Kiyomi, M., Okamoto, Y., and Saitoh, T. (2012) Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data. In: Klasing, R. (ed.) SEA 2012: the 11th International Symposium on Experimental Algorithms, Bordeaux, France, Jun. 2012. Lecture Notes in Computer Science, vol 7276. Springer Berlin Heidelberg, p 248-259. doi:10.1007/978-3-642-30850-5_22 (Problem 218)
[Kloks1994]
Kloks, T and Kratsch, D (1994) Finding all minimal separators of a graph. In: Enjalbert, P., Mayr, E. W., and Wagner, K. W. (eds.) STACS 1994: the 11th Annual Symposium on Theoretical Aspects of Computer Science, France, Feb. 1994. Lecture Notes in Computer Science, vol 775. Springer Berlin Heidelberg, p 759-768. doi:10.1007/3-540-57785-8_188 (Problem 181)
[Kloks1998]
Kloks, T. and Kratsch, D. (1998) Listing All Minimal Separators of a Graph. SIAM Journal on Computing 27(3):605-613. doi:10.1137/S009753979427087X (Problem 316)
[Knuth1974]
Knuth, D. E. and Szwarcfiter, J. L. (1974) A structured program to generate all topological sorting arrangements. Information Processing Letters 2(6):153-157. doi:10.1016/0020-0190(74)90001-5 (Problem 78)
[Knuth1979]
Knuth, D. E (1979) Lexicographic permutations with restrictions. Discrete Applied Mathematics 1(1-2):117-125. doi:10.1016/0166-218X(79)90018-0 (Problem 386)
[Koch2001]
Koch, I. (2001) Enumerating All Connected Maximal Common Subgraphs in Two Graphs. Theoretical Computer Science 250(1-2):1-30. doi:10.1016/S0304-3975(00)00286-3 (Problem 299)
[Koda1993]
Koda, Y. and Ruskey, F. (1993) A Gray Code for the Ideals of a Forest Poset. Journal of Algorithms 15(2):324-340. doi:10.1006/jagm.1993.1044 (Problem 342)
[Korsh1994]
Korsh, J. F. (1994) Loopless generation of k-ary tree sequences. Information Processing Letters 52(5):243-247. doi:10.1016/0020-0190(94)00149-9 (Problem 337)
[Korsh1998]
Korsh, J. F. and Lipschutz, S. (1998) Shifts and loopless generation of k-ary trees. Information Processing Letters 65(5):235-240. doi:10.1016/S0020-0190(97)00215-9 (Problem 313)
[Kroft1967b]
Kroft, D. (1967) All paths through a maze. Proceedings of the IEEE 55(1):88-90. doi:10.1109/PROC.1967.5389 (Problem 423)
[Krzywkowski2013]
Krzywkowski, M. (2013) An algorithm for listing all minimal 2-dominating sets of a tree. In: Fellows, M., Tan, X., and Zhu, B. (eds.) FAW-AAIM 2013: the 3rd Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, Dalian, China, Jun. 2013. Lecture Notes in Computer Science, vol 7924. Springer Berlin Heidelberg, p 12-16. doi:10.1007/978-3-642-38756-2_4 (Problem 189)
[Laumond1985]
Laumond, J.-P. (1985) Enumeration of articulation pairs of a planar graph. Information Processing Letters 21(4):173-179. doi:10.1016/0020-0190(85)90055-9 (Problem 365)
[Lawler1972]
Lawler, E. L. (1972) A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem. Management Science 18(7):401-405. doi:10.1287/mnsc.18.7.401 (Problem 79)
[Leung1984]
Leung, J. Y.-T. (1984) Fast Algorithms for Generating All Maximal Independent Sets of Interval, Circular-Arc and Chordal Graphs. Journal of Algorithms 5(1):22-35. doi:10.1016/0196-6774(84)90037-3 (Problem 367, Problem 368, Problem 369)
[Li2003]
Li, Z.-J. and Nakano, S. (2003) Generating Biconnected Plane Quadrangulations. IEICE transactions on information and systems E86-D(4):698-703 (Problem 168)
[Loukakis1981]
Loukakis, E. and Tsouros, C. (1981) A Depth First Search Algorithm to Generate the Family of Maximal Independent Sets of a Graph Lexicographically. Computing 27(4):349-366. doi:10.1007/BF02277184 (Problem 376)
[Lucas1987]
Lucas, J. M. (1987) The Rotation Graph of Binary Trees Is Hamiltonian. Journal of Algorithms 8(4):503-535. doi:10.1016/0196-6774(87)90048-4 (Problem 357)
[Lucas1993]
Lucas, J. M., Vanbaronaigien, D.R., and Ruskey, F. (1993) On Rotations and the Generation of Binary Trees. Journal of Algorithms 15(3):343-366. doi:10.1006/jagm.1993.1045 (Problem 343)
[Makino2004]
Makino, K. and Uno, T. (2004) New algorithms for enumerating all maximal cliques. In: Hagerup, T. and Katajainen, J. (eds.) SWAT 2004: the 9th Scandinavian Workshop on Algorithm Algorithm Theory, Humleb\ae k, Denmark, Jul. 2004. Lecture Notes in Computer Science, vol 3111. Springer Berlin Heidelberg, p 260-272. doi:10.1007/978-3-540-27810-8_23 (Problem 20, Problem 21)
[Martelli1976a]
Martelli, A. (1976) A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph. Journal of the ACM 23(1):58-73. doi:10.1145/321921.321928 (Problem 399)
[Martins1984]
Martins, E. Q. V. (1984) An algorithm for ranking paths that may contain cycles. European Journal of Operational Research 18(1):123-130. doi:10.1016/0377-2217(84)90269-8 (Problem 80)
Masada, T., Imai, H., and Imai, K. (1996) Enumeration of regular triangulations. In: Whitesides, S. (ed.) SCG 1996: the 12th annual symposium on Computational geometry, Philadelphia, PA, USA, May. 1996. ACM Press, p 224-233. doi:10.1145/237218.237373 (Problem 81, Problem 82)
[Mateti1976a]
Mateti, P. and Deo, N. (1976) On Algorithms for Enumerating All Circuits of a Graph. SIAM Journal on Computing 5(1):90-99. doi:10.1137/0205007 (Problem 400)
[Matsui1994]
Matsui, T., Tamura, A., and Ikebe, Y. (1994) Algorithms for finding a Kth best valued assignment. Discrete Applied Mathematics 50(3):283-296. doi:10.1016/0166-218X(92)00175-L (Problem 85)
[Matsui1996a]
Matsui, Y. and Uno, T. (1996) A simple and fast algorithm for enumerating all edge colorings of a bipartite graph. In: Korea-Japan Joint Workshop on Algorithms and Computation, KAIST,Taejon,Korea, Aug. 1996. p 81-87 (Problem 87)
[Matsui1996b]
Matsui, Y. and Matsui, T. (1996) Enumeration Algorithm for the Edge Coloring Problem on Bipartite Graphs. Springer Berlin Heidelberg (Problem 86)
[Matsui1997]
Matsui, T. (1997) A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs. Algorithmica 18(4):530-543. doi:10.1007/PL00009171 (Problem 83, Problem 84)
[Matsui2008]
Matsui, Y., Uehara, R., and Uno, T. (2008) Enumeration of Perfect Sequences of Chordal Graph. In: Hong, S.-H., Nagamochi, H., and Fukunaga, T. (eds.) ISAAC 2008: the 19th International Symposium on Algorithms and Computation, Gold Coast, Australia, Dec. 2008. Lecture Notes in Computer Science, vol 5369. Springer Berlin Heidelberg, p 859-870. doi:10.1007/978-3-540-92182-0_75 (Problem 241)
[Matsui2010]
Matsui, Y., Uehara, R., and Uno, T. (2010) Enumeration of the Perfect Sequences of a Chordal Graph. Theoretical Computer Science 411(40-42):3635-3641. doi:10.1016/j.tcs.2010.06.007 (Problem 38)
[Mayeda1965a]
Mayeda, W. and Seshu, S. (1965) Generation of Trees without Duplications. IEEE Transactions on Circuit Theory 12(2):181-185. doi:10.1109/TCT.1965.1082432 (Problem 384)
[Mayr1992]
Mayr, E. W and Plaxton, C G. (1992) On the spanning trees of weighted graphs. Combinatorica 12(4):433-447. doi:10.1007/BF01305236 (Problem 88)
[Mazoit2006]
Mazoit, F. (2006) Listing all the minimal separators of a 3-connected planar graph. Discrete Mathematics 306(3):372-380. doi:10.1016/j.disc.2005.12.007 (Problem 275)
[McKay1970]
McKay, J. K. S. (1970) Algorithm 371: Partitions in natural order [A1]. Communications of the ACM 13(1):52. doi:10.1145/361953.361980 (Problem 411)
[McKay1998]
McKay, B. D. (1998) Isomorph-Free Exhaustive Generation. Journal of Algorithms 26(2):306-324. doi:10.1006/jagm.1997.0898 (Problem 314)
[Megiddo1981]
Megiddo, N., Tamir, A., Zemel, E., and Chandrasekaran, R. (1981) An \$O(n\backslash log \^{}2 n)\$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems. SIAM Journal on Computing 10(2):328-337. doi:10.1137/0210023 (Problem 89)
[Minty1965]
Minty, G. J. (1965) A Simple Algorithm for Listing All the Trees of a Graph. IEEE Transactions on Circuit Theory 12(1):120. doi:10.1109/TCT.1965.1082385 (Problem 1)
[Minty1980]
Minty, G. J. (1980) On maximal independent sets of vertices in claw-free graphs. Journal of Combinatorial Theory, Series B 28(3):284-304. doi:10.1016/0095-8956(80)90074-X (Problem 381)
[Mulligan1972]
Mulligan, G. D. and Corneil, D. G. (1972) Corrections to Bierstone's Algorithm for Generating Cliques. Journal of the ACM 19(2):244-247. doi:10.1145/321694.321698 (Problem 410)
[Murty1968]
Murty, K. G. (1968) Letter to the Editor--An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research 16(3):682-687. doi:10.1287/opre.16.3.682 (Problem 90)
[Nakano2001]
Nakano, S. (2001) Efficient Generation of Triconnected Plane Triangulations. In: Wang, J. (ed.) COCOON 2001: the 7th Annual International Conference on Computing and Combinatorics, Guilin, China, Aug. 2001. Lecture Notes in Computer Science, vol 2108. Springer Berlin Heidelberg, p 131-141. doi:10.1007/3-540-44679-6_15 (Problem 160, Problem 161, Problem 162)
[Nakano2001a]
Nakano, S. (2001) Enumerating Floorplans with n Rooms. In: Eades, P. and Takaoka, T. (eds.) ISAAC 2001: the 12th International Symposium on Algorithms and Computation, Christchurch, New Zealand,, Dec. 2001. Lecture Notes in Computer Science, vol 2223. Springer Berlin Heidelberg, p 107-115. doi:10.1007/3-540-45678-3_10 (Problem 155, Problem 156, Problem 157)
[Nakano2002]
Nakano, S. (2002) Efficient generation of plane trees. Information Processing Letters 84(3):167-172. doi:10.1016/S0020-0190(02)00240-5 (Problem 149, Problem 150, Problem 151, Problem 152, Problem 153)
[Nakano2003]
Nakano, S. and Uno, T. (2003) Efficient generation of rooted trees. National Institute for Infomatics, Tech. Rep. NII-2003-005E. (Problem 154)
[Nakano2004]
Nakano, S. and Uno, T. (2004) Constant TIme Generation of Trees with Specified Diameter. In: Hromkovi\v{c}, J., Nagl, M., and Westfechtel, B. (eds.) WG 2004: the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, Honnef, Germany, Jun. 2004. Lecture Notes in Computer Science, vol 3353. Springer Berlin Heidelberg, p 33-45. doi:10.1007/978-3-540-30559-0_3 (Problem 148)
[Nakano2004a]
Li, Z. and Nakano, S. (2001) Efficient Generation of Plane Triangulations without Repetitions. In: Orejas, F., Spirakis, P. G., and van Leeuwen, J. (eds.) ICALP 2001: the 28th International Colloquium on Automata, Languages and Programming, Crete, Greece, Jul. 2001. Lecture Notes in Computer Science, vol 2076. Springer Berlin Heidelberg, p 433-443. doi:10.1007/3-540-48224-5_36 (Problem 144, Problem 145, Problem 146, Problem 147)
[Nakano2004b]
Nakano, S. and Uno, T. (2004) More Efficient Generation of Plane Triangulations. In: Liotta, G. (ed.) the11th International Symposium on Graph Drawing - GD 2004, Perugia, Italy, Sep. 2004. Lecture Notes in Computer Science, vol 2912. Springer Berlin Heidelberg, p 273-282. doi:10.1007/978-3-540-24595-7_25 (Problem 170)
[Nakano2005a]
Nakano, S. and Uno, T. (2005) Generating colored trees. In: Kratsch, D. (ed.) WG 2005: the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Metz, France, Jun. 2005. Lecture Notes in Computer Science, vol 3787. Springer Berlin Heidelberg, p 249-260. doi:10.1007/11604686_22 (Problem 158)
[Nakano2009]
Nakano, S. (2009) Listing All Trees with Specified Degree Sequence (Acceleration and Visualization of Computation for Enumeration Problems). 数理解析研究所講究録 1644:55-62 (Problem 166)
[Narayana1971]
Narayana, T.V, Mathsen, R.M, and Sarangi, J (1971) An algorithm for generating partitions and its applications. Journal of Combinatorial Theory, Series A 11(1):54-61. doi:10.1016/0097-3165(71)90007-0 (Problem 408, Problem 409)
[Nutov2009]
Nutov, Z. (2009) Listing minimal edge-covers of intersecting families with applications to connectivity problems. Discrete Applied Mathematics 157(1):112-117. doi:10.1016/j.dam.2008.04.026 (Problem 234, Problem 235, Problem 236, Problem 237, Problem 238, Problem 239)
[Okamoto2005a]
Okamoto, Y, Uno, T, and Uehara, R (2005) Linear time counting algorithms for independent sets in chordal graphs. In: Kratsch, D. (ed.) WG 2005: the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, Metz, France, Jun. 2005. Lecture Notes in Computer Science, vol 3787. Springer Berlin Heidelberg, p 433-444. doi:10.1007/11604686_38 (Problem 283, Problem 284, Problem 285)
[Okamoto2008]
Okamoto, Y., Uno, T., and Uehara, R. (2008) Counting the number of independent sets in chordal graphs. Journal of Discrete Algorithms 6(2):229-242. doi:10.1016/j.jda.2006.07.006 (Problem 26, Problem 27, Problem 28)
[Ono2005]
Ono, A. and Nakano, S. (2005) Constant Time Generation of Linear Extensions. In: Li\'{s}kiewicz, M. and Reischuk, R. (eds.) FCT 2005: the 15th International Symposium on Fundamentals of Computation Theory, L\"{u}beck, Germany, Aug. 2005. Lecture Notes in Computer Science, vol 3623. Springer Berlin Heidelberg, p 445-453. doi:10.1007/11537311_39 (Problem 39)
[Pallo1987]
Pallo, J. (1987) Generating Trees With N Nodes and M Leaves. International Journal of Computer Mathematics 21(2):133-144. doi:10.1080/00207168708803562 (Problem 360)
[Pan2008]
Pan, L. and Santos, E. E. (2008) An anytime-anywhere approach for maximal clique enumeration in social network analysis. In: the IEEE International Conference on Systems, Man and Cybernetics - SMC 2008, Singapore, Oct. 2008. IEEE, p 3529-3535. doi:10.1109/ICSMC.2008.4811845 (Problem 247)
[Pardalos1994]
Pardalos, P. M. and Xue, J. (1994) The maximum clique problem. Journal of Global Optimization 4(3):301-328. doi:10.1007/BF01098364 (Problem 338)
[Parvez2009]
Parvez, M. T., Rahman, M. S., and Nakano, S. (2009) Generating all triangulations of plane graphs : Extended abstract. In: Das, S. and Uehara, R. (eds.) WALCOM 2009: the 3rd International Workshop on Algorithms and Computation, Kolkata, India, Feb. 2009. Lecture Notes in Computer Science, vol 5431. Springer Berlin Heidelberg, p 151-164. doi:10.1007/978-3-642-00202-1_14 (Problem 171, Problem 172, Problem 173)
[Ponstein1966]
Ponstein, J. (1966) Self-Avoiding Paths and the Adjacency Matrix of a Graph. SIAM Journal on Applied Mathematics 14(3):600-609. doi:10.1137/0114051 (Problem 393, Problem 394)
[Proskurowski1980]
Proskurowski, A. (1980) On the Generation of Binary Trees. Journal of the ACM 27(1):1-2. doi:10.1145/322169.322170 (Problem 380)
[Proskurowski1985]
Proskurowski, A. and Ruskey, F. (1985) Binary Tree Gray Codes. Journal of Algorithms 6(2):225-238. doi:10.1016/0196-6774(85)90040-9 (Problem 364)
[Proskurowski1998]
Proskurowski, A., Ruskey, F., and Smith, M. (1998) Analysis of Algorithms for Listing Equivalence Classes of k -ary Strings. SIAM Journal on Discrete Mathematics 11(1):94-109. doi:10.1137/S0895480192234009 (Problem 317)
[Provan1996]
Provan, J. S. and Shier, D. R. (1996) A paradigm for listing (s, t)-cuts in graphs. Algorithmica 15(4):351-372. doi:10.1007/BF01961544 (Problem 91, Problem 92, Problem 93, Problem 94, Problem 95, Problem 96, Problem 97, Problem 98, Problem 99, Problem 100)
[Pruesse1991a]
Pruesse, G. and Ruskey, F. (1991) Generating the Linear Extensions of Certain Posets by Transpositions. SIAM Journal on Discrete Mathematics 4(3):413-422. doi:10.1137/0404037 (Problem 349)
[Pruesse1994]
Pruesse, G. and Ruskey, F. (1994) Generating Linear Extensions Fast. SIAM Journal on Computing 23(2):373-386. doi:10.1137/S0097539791202647 (Problem 101)
[Ramon2007]
Ramon, J. and Nijssen, S. (2007) General Graph Refinement with Polynomial Delay. In: Mining and Learning with Graphs - MLG 2007, Florence, Italy, Aug. 2007. p 4 (Problem 261)
[Ramon2009]
Ramon, J. and Nijssen, S. (2009) Polynomial-Delay Enumeration of Monotonic Graph Classes. The Journal of Machine Learning Research 10:907-929 (Problem 231)
[Rao1969]
{Bapeswara Rao}, V.V. and Murti, V.G.K. (1969) Enumeration of all circuits of a graph. Proceedings of the IEEE 57(4):700-701. doi:10.1109/PROC.1969.7032 (Problem 414)
[Rasmussen1995]
Rasmussen, D., Savage, C. D, and West, D. B (1995) Gray code enumeration of families of integer partitions. Journal of Combinatorial Theory, Series A 70(2):201-229. doi:10.1016/0097-3165(95)90090-X (Problem 332, Problem 333)
Read, R. C. and Tarjan, R. E. (1975) Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3):237-252 (Problem 102, Problem 103, Problem 104, Problem 105, Problem 106)
[Rosen1991]
Rosen, J.B., Sun, S.-Z., and Xue, G.-L. (1991) Algorithms for the Quickest Path Problem and the Enumeration of Quickest Paths. Computers \& Operations Research 18(6):579-584. doi:10.1016/0305-0548(91)90063-W (Problem 350)
[Rotem1978a]
Rotem, D. and Varol, Y. L. (1978) Generation of Binary Trees from Ballot Sequences. Journal of the ACM 25(3):396-404. doi:10.1145/322077.322082 (Problem 403)
[Rotem1981]
Rotem, D. and Urrutia, J. (1981) Finding Maximum Cliques In Circle Graphs. Networks 11(3):269-278. doi:10.1002/net.3230110305 (Problem 107)
[Ruskey1977]
Ruskey, F. and Hu, T. C. (1977) Generating Binary Trees Lexicographically. SIAM Journal on Computing 6(4):745-758. doi:10.1137/0206055 (Problem 389)
[Ruskey1978a]
Ruskey, F. (1978) Generating T -Ary Trees Lexicographically. SIAM Journal on Computing 7(4):424-439. doi:10.1137/0207034 (Problem 390)
[Ruskey1981]
Ruskey, F. (1981) Listing and Counting Subtrees of a Tree. SIAM Journal on Computing 10(1):141-150. doi:10.1137/0210011 (Problem 3)
[Ruskey1988]
Ruskey, F. (1988) Adjacent Interchange Generation of Combinations. Journal of Algorithms 9(2):162-180. doi:10.1016/0196-6774(88)90036-3 (Problem 355)
[Ruskey1990]
Ruskey, F. and Proskurowski, A. (1990) Generating Binary Trees by Transpositions. Journal of Algorithms 11(1):68-84. doi:10.1016/0196-6774(90)90030-I (Problem 352)
[Ruskey1992]
Ruskey, F., Savage, C., and {Min Yih Wang}, T. (1992) Generating Necklaces. Journal of Algorithms 13(3):414-430. doi:10.1016/0196-6774(92)90047-G (Problem 41)
[Ruskey1992a]
Ruskey, F. (1992) Generating linear extensions of posets by transpositions. Journal of Combinatorial Theory, Series B 54(1):77-101. doi:10.1016/0095-8956(92)90067-8 (Problem 346)
[Ruskey1993]
Ruskey, F. (1993) Simple combinatorial Gray codes constructed by reversing sublists. In: Ng, K. W., Raghavan, P., Balasubramanian, N. V., and Chin, F. Y. L. (eds.) ISAAC 1993: the 4th International Symposium on Algorithms and Computation, Hong Kong, China, Dec. 1993. Lecture Notes in Computer Science, vol 762. Springer Berlin Heidelberg, p 201-208. doi:10.1007/3-540-57568-5_250 (Problem 344)
[Ruskey1999]
Ruskey, F. and Sawada, J. (1999) An Efficient Algorithm for Generating Necklaces With Fixed Density. SIAM Journal on Computing 29(2):671-684. doi:10.1137/S0097539798344112 (Problem 42)
[Ruskey2000a]
Ruskey, F. and Sawada, J. (2000) Generating necklaces and strings with forbidden substrings. In: Du, D.-Z., Eades, P., Estivill-Castro, V., Lin, X., and Sharma, A. (eds.) COCOON 2000: the 6th Annual International Conference on Computing and Combinatorics, Sydney, Australia, Jul. 2000. Lecture Notes in Computer Science, vol 1858. Springer Berlin Heidelberg, p 330-339. doi:10.1007/3-540-44968-X_33 (Problem 310, Problem 311, Problem 312)
[Sacomoto2013b]
Sacomoto, G., Lacroix, V., and Sagot, M. (2013) A Polynomial Delay Algorithm for the Enumeration of Bubbles with Length Constraints in Directed Graphs and Its Application to the Detection of Alternative Splicing in RNA-seq Data. In: Darling, A. and Stoye, J. (eds.) WABI 2013: the 13th International Workshop on Algorithms in Bioinformatics, Sophia Antipolis, France, Sep. 2013. Lecture Notes in Computer Science, vol 8126. Springer Berlin Heidelberg, p 99-111. doi:10.1007/978-3-642-40453-5_9 (Problem 191)
[Saitoh2010]
Saitoh, T., Otachi, Y., Yamanaka, K., and Uehara, R. (2012) Random generation and enumeration of bipartite permutation graphs. Journal of Discrete Algorithms 10(1):84-97. doi:10.1016/j.jda.2011.11.001 (Problem 37, Problem 123)
[Saruwatari1993]
Saruwatari, Y. and Matsui, T. (1993) A Note on \$K\$-Best Solutions to the Chinese Postman Problem. SIAM Journal on Optimization 3(4):726-733. doi:10.1137/0803037 (Problem 108)
[Savage1989]
Savage, C. D (1989) Gray Code Sequences of Partitions. Journal of Algorithms 10(4):577-595. doi:10.1016/0196-6774(89)90007-2 (Problem 353)
[Savage1997]
Savage, C. (1997) A Survey of Combinatorial Gray Codes. SIAM Review 39(4):605-629. doi:10.1137/S0036144595295272 (Problem 330)
Sawada, J. (2001) Generating Bracelets in Constant Amortized Time. SIAM Journal on Computing 31(1):259-268. doi:10.1137/S0097539700377037 (Problem 43)
Sawada, J. (2002) A Fast Algorithm for Generating Nonisomorphic Chord Diagrams. SIAM Journal on Discrete Mathematics 15(4):546-561. doi:10.1137/S0895480100377970 (Problem 296)
Sawada, J. and Ruskey, F. (2003) Generating Lyndon Brackets.. Journal of Algorithms 46(1):21-26. doi:10.1016/S0196-6774(02)00286-9 (Problem 293)
Sawada, J. (2003) A Fast Algorithm to Generate Necklaces With Fixed Content. Theoretical Computer Science 301(1-3):477-489. doi:10.1016/S0304-3975(03)00049-5 (Problem 294)
Sawada, J. (2006) Generating rooted and free plane trees. ACM Transactions on Algorithms 2(1):1-13. doi:10.1145/1125994.1125995 (Problem 276, Problem 277)
[Schmidt2009]
Schmidt, M. C., Samatova, N. F., Thomas, K., and Park, B.-H. (2009) A Scalable, Parallel Algorithm for Maximal Clique Enumeration. Journal of Parallel and Distributed Computing 69(4):417-428. doi:10.1016/j.jpdc.2009.01.003 (Problem 227)
[Schwikowski2002]
Schwikowski, B. and Speckenmeyer, E. (2002) On enumerating all minimal solutions of feedback problems. Discrete Applied Mathematics 117(1-3):253-265. doi:10.1016/S0166-218X(00)00339-5 (Problem 22, Problem 23, Problem 24)
[Segoufin2013]
Segoufin, L. (2013) Enumerating with constant delay the answers to a query. In: Tan, W. C. (ed.) ICDT 2013: the 16th International Conference on Database Theory, Genoa, Italy, Mar. 2013. ACM Press, p 10-20. doi:10.1145/2448496.2448498 (Problem 197)
[Seidel1990]
Seidel, R. (1991) Small-dimensional linear programming and convex hulls made easy. Discrete \& Computational Geometry 6(1):423-434. doi:10.1007/BF02574699 (Problem 111)
[Semba1984]
Semba, I. (1984) An Efficient Algorithm for Generating all Partitions of the Set\{1, 2, ..., n\}. Journal of information processing 7(1):41-42 (Problem 370)
[Setiawan2011]
Setiawan, A. and Nakano, S. (2011) Listing all st-orientations. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A(10):1965-1970. doi:10.1587/transfun.E94.A.1965 (Problem 174)
[Shen1997]
Shen, H. and Liang, W. (1997) Efficient Enumeration of All Minimal Separators in a Graph. Theoretical Computer Science 180(1-2):169-180. doi:10.1016/S0304-3975(97)83809-1 (Problem 72, Problem 320)
[Shier1979]
Shier, D. R. (1979) On algorithms for finding the k shortest paths in a network. Networks 9(3):195-214. doi:10.1002/net.3230090303 (Problem 109)
[Shioura1995]
Shioura, A. and Tamura, A. (1995) Efficiently Scanning all Spanning Trees of an Undirected Graph. Journal of the Operations Research Society of Japan 38(3):331-344. doi:10.1.1.30.4555 (Problem 110)
[Shioura1997]
Shioura, A., Tamura, A., and Uno, T. (1997) An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs. SIAM Journal on Computing 26(3):678-692. doi:10.1137/S0097539794270881 (Problem 15)
[Sorensen2005]
S\"{o}rensen, K. and Janssens, G. K. (2005) An algorithm to generate all spanning trees of a graph in order of increasing cost. Pesquisa Operacional 25(2):219-229. doi:10.1590/S0101-74382005000200004 (Problem 286)
[Stix2004]
Stix, V. (2004) Finding All Maximal Cliques in Dynamic Graphs. Computational Optimization and Applications 27(2):173-186. doi:10.1023/B:COAP.0000008651.28952.b6 (Problem 180, Problem 289)
[Stojmenovic2007]
Stojmenovi\'{c}, I. and Zoghbi, A. (2007) Fast Algorithms for Genegrating Integer Partitions. International Journal of Computer Mathematics 70(2):319-332. doi:10.1080/00207169808804755 (Problem 258)
[Strozecki2010a]
Strozecki, Y. (2010) Enumeration of the Monomials of a Polynomial and Related Complexity Classes. In: Hlin\v{e}n\'{y}, P. and Ku\v{c}era, A. (eds.) MFCS 2010: the 35th International Symposium on Mathematical Foundations of Computer Science, Brno, Czech Republic, Aug. 2010. Lecture Notes in Computer Science, vol 6281. Springer Berlin Heidelberg, p 629-640. doi:10.1007/978-3-642-15155-2_55 (Problem 211, Problem 212)
[Syso1981]
Sysło, M. M. (1981) An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph. SIAM Journal on Computing 10(4):797-808. doi:10.1137/0210062 (Problem 8)
[Szwarcfiter2003b]
Szwarcfiter, JL (2003) Generating all forest extensions of a partially ordered set. In: Petreschi, R., Persiano, G., and Silvestri, R. (eds.) CIAC 2003: the 5th Italian Conference on Algorithms and Complexity, Rome, Italy, May. 2003. Lecture Notes in Computer Science, vol 2653. Springer Berlin Heidelberg, p 132-139. doi:10.1007/3-540-44849-7_19 (Problem 295)
[Takagi2004]
Takagi, M. and Nakano, S. (2004) Listing all rectangular drawings with certain properties. Systems and Computers in Japan 35(4):1-8. doi:10.1002/scj.10563 (Problem 167)
[Takeuchi]
Takeuchi, F. and Imai, H. (1997) Enumerating triangulations for products of two simplices and for arbitrary configurations of points. In: Jiang, T. and Lee, D. T. (eds.) COCOON 1997: the 3rd Annual International Conference on Computing and Combinatorics, Shanghai, China, Aug. 1997. Lecture Notes in Computer Science, vol 1276. Springer Berlin Heidelberg, p 470-481. doi:10.1007/BFb0045114 (Problem 112, Problem 113)
[Tamaki2000]
Tamaki, H. (2000) Space-efficient enumeration of minimal transversals of a hypergraph (in Japanese, 極小横断列挙のメモリ効率の良いアルゴリズム). In: アルゴリズム研究会報告, Nov. 2000. 一般社団法人情報処理学会, p 29-36 (Problem 303)
[Tarjan1973]
Tarjan, R. (1973) Enumeration of the Elementary Circuits of a Directed Graph. SIAM Journal on Computing 2(3):211-216. doi:10.1137/0202017 (Problem 6)
[Tiernan1970]
Tiernan, J. C. (1970) An efficient search algorithm to find the elementary circuits of a graph. Communications of the ACM 13(12):722-726. doi:10.1145/362814.362819 (Problem 391)
[Tomita2006]
Tomita, E., Tanaka, A., and Takahashi, H. (2006) The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Theoretical Computer Science 363(1):28-42. doi:10.1016/j.tcs.2006.06.015 (Problem 278)
[Trojanowski1978]
Trojanowski, A. E. (1978) Ranking and Listing Algorithms for k -Ary Trees. SIAM Journal on Computing 7(4):492-509. doi:10.1137/0207039 (Problem 401)
[Tsukiyama1977a]
Tsukiyama, S., Ide, M., Ariyoshi, H., and Shirakawa, I. (1977) A New Algorithm for Generating All the Maximal Independent Sets. SIAM Journal on Computing 6(3):505-517. doi:10.1137/0206036 (Problem 25)
[Tsukiyama1980]
Tsukiyama, S., Shirakawa, I., Ozaki, H., and Ariyoshi, H. (1980) An Algorithm to Enumerate All Cutsets of a Graph in Linear Time Per Cutset. Journal of the ACM 27(4):619-632. doi:10.1145/322217.322220 (Problem 114)
[Uno1996]
Uno, T. (1996) An algorithm for enumerating all directed spanning trees in a directed graph. In: Asano, T., Igarashi, Y., Nagamochi, H., Miyano, S., and Suri, S. (eds.) ISAAC 1996: the 7th International Symposium on Algorithms and Computation, Osaka, Japan, Dec. 1996. Lecture Notes in Computer Science, vol 1178. Springer Berlin Heidelberg, p 166-173. doi:10.1007/BFb0009492 (Problem 115)
[Uno1997]
Uno, T. (1997) Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs. In: Leong, H. W., Imai, H., and Jain, S. (eds.) ISAAC 1997: the 8th International Symposium on Algorithms and Computation, Singapore, Dec. 1997. Lecture Notes in Computer Science, vol 1350. Springer Berlin Heidelberg, p 92-101. doi:10.1007/3-540-63890-3_11 (Problem 32)
[Uno1998]
Uno, T. (1999) A New Approach for Speeding Up Enumeration Algorithms and Its Application for Matroid Bases. In: Asano, T., Imai, H., Lee, D. T., Nakano, S., and Tokuyama, T. (eds.) COCOON 1999: the 5th Annual International Conference on Computing and Combinatorics, Tokyo, Japan, Jul. 1999. Lecture Notes in Computer Science, vol 1627. Springer Berlin Heidelberg, p 349-359. doi:10.1007/3-540-48686-0_35 (Problem 117, Problem 118, Problem 119)
[Uno1998a]
Uno, T. (1998) New Approach for Speeding Up Enumeration Algorithms. In: Chwa, K.-Y. and Ibarra, O. H. (eds.) ISAAC 1998: the 9th International Symposium on Algorithms and Computation, Taejon, Korea, Dec. 1998. Lecture Notes in Computer Science, vol 1533. Springer Berlin Heidelberg, p 287-296. doi:10.1007/3-540-49381-6_31 (Problem 120)
[Uno2001]
Uno, T. (2001) A Fast Algorithm for Enumeration of Maximal Matchings in General Graphs. Journal of National Institute of Informatics 3:89-97 (Problem 116)
[Uno2008a]
Uno, T. (2010) An efficient algorithm for solving pseudo clique enumeration problem. Algorithmica 56(1):3-16. doi:10.1007/s00453-008-9238-3 (Problem 254)
[Unoc]
Uno, T. and Satoh, H. (2014) An Efficient Algorithm for Enumerating Chordless Cycles and Chordless Paths. In: D\v{z}eroski, S., Panov, P., Kocev, D., and Todorovski, L. (eds.) DS 2014: the 17th International Conference on Discovery Science, Bled, Slovenia, Oct. 2014. Lecture Notes in Computer Science, vol 8777. Springer Berlin Heidelberg, p 313-324. doi:10.1007/978-3-319-11812-3_27 (Problem 12, Problem 14)
[VanBaronaigien1988]
van Baronaigien, D.R. and Ruskey, F. (1988) Generating t-ary trees in A-order. Information Processing Letters 27(4):205-213. doi:10.1016/0020-0190(88)90027-0 (Problem 354)
[VanBaronaigien1991]
van Baronaigien, D.R. (1991) A loopless algorithm for generating binary tree sequences. Information Processing Letters 39(4):189-194. doi:10.1016/0020-0190(91)90178-K (Problem 351)
[Varol1981]
Varol, Y. L. (1981) An Algorithm to Generate All Topological Sorting Arrangements. The Computer Journal 24(1):83-84. doi:10.1093/comjnl/24.1.83 (Problem 378)
[Walsh1998]
Walsh, T. R. (1998) Generation of Well-Formed Parenthesis Strings in Constant Worst-Case Time. Journal of Algorithms 29(1):165-173. doi:10.1006/jagm.1998.0960 (Problem 315)
[Wang1996]
Wang, T. M. Y. and Savage, C. D. (1996) A Gray Code for Necklaces of Fixed Density. SIAM Journal on Discrete Mathematics 9(4):654-673. doi:10.1137/S089548019528143X (Problem 329)
[Wang2009]
Wang, J., Chen, B, Feng, Q., and Chen, J. (2009) An efficient fixed-parameter enumeration algorithm for weighted edge dominating set. In: Deng, X., Hopcroft, J. E., and Xue, J. (eds.) FAW 2009: the 3rd International Workshop on Frontiers in Algorithmics, Hefei, China, Jun. 2009. Lecture Notes in Computer Science, vol 5598. Springer Berlin Heidelberg, p 237-250. doi:10.1007/978-3-642-02270-8_25 (Problem 228)
[Wasa2010]
Wasa, K., Arimura, H., and Uno, T. (2014) Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph. In: Ahn, H.-K. and Shin, C.-S. (eds.) ISAAC 2014: the 25th International Symposium on Algorithms and Computation, Jeonju, Korea, Dec. 2014. Lecture Notes in Computer Science, vol 6506. Springer Berlin Heidelberg, p 488. doi:10.1007/978-3-319-13075-0_8 (Problem 377)
[Wasa2012b]
Wasa, K., Kaneta, Y., Uno, T., and Arimura, H. (2012) Constant Time Enumeration of Bounded-Size Subtrees in Trees and Its Application. In: Gudmundsson, J., Mestre, J., and Viglas, T. (eds.) COCOON 2012: the 18th Annual International Conference on Computing and Combinatorics, Sydney, Australia, Aug. 2012. Lecture Notes in Computer Science, vol 7434. Springer Berlin Heidelberg, p 347-359. doi:10.1007/978-3-642-32241-9_30 (Problem 4)
[Wasa2013]
Wasa, K., Uno, T., Hirata, K., and Arimura, H. (2013) Polynomial delay and space discovery of connected and acyclic sub-hypergraphs in a hypergraph. In: F\"{u}rnkranz, J., H\"{u}llermeier, E., and Higuchi, T. (eds.) DS 2013: the 16th International Conference on Discovery Science, Singapore, Oct. 2013. Lecture Notes in Computer Science, vol 8140. Springer Berlin Heidelberg, p 308-323. doi:10.1007/978-3-642-40897-7_21 (Problem 176)
[Watanabe1981]
Watanabe, O. (1981) A fast algortihm for finding all shortest paths. Information Processing Letters 13(1):1-3. doi:10.1016/0020-0190(81)90139-3 (Problem 179)
[Weinblatt1972]
Weinblatt, H. (1972) A New Search Algorithm for Finding the Simple Cycles of a Finite Directed Graph. Journal of the ACM 19(1):43-56. doi:10.1145/321679.321684 (Problem 407, Problem 413)
[Welch1965]
Welch, J T (1965) Ccyle Algorithms for Undirected Linear Graphs and Some immediate Applications. In: Proceedings of the 1965 20th national conference, New York, New York, USA, Aug. 1965. ACM Press, p 296-301. doi:10.1145/800197.806053 (Problem 429)
[Welch1966]
Welch, J. T. (1966) A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs. Journal of the ACM 13(2):205-210. doi:10.1145/321328.321331 (Problem 422)
[Wells1961]
Wells, M. B. (1961) Generation of permutations by transposition. Mathematics of Computation 15(74):192-195. doi:10.1090/S0025-5718-1963-0159764-2 (Problem 382)
[Wettstein2014]
Wettstein, M. (2014) Counting and Enumerating Crossing-free Geometric Graphs. In: Annual Symposium on Computational Geometry - SOCG'14, New York, New York, USA, Jun. 2014. ACM Press, p 1-10. doi:10.1145/2582112.2582145 (Problem 426)
[White1970]
White, J. S. (1970) Algorithm 374: Restricted partition generator [A1]. Communications of the ACM 13(2):120. doi:10.1145/362007.362046 (Problem 412)
[Wild2008]
Wild, M. (2008) Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion. Journal of Discrete Algorithms 6(1):93-102. doi:10.1016/j.jda.2007.01.005 (Problem 243, Problem 244, Problem 245, Problem 246)
[Wild2013]
Wild, M. (2013) Output-Polynomial Enumeration of All Fixed-Cardinality Ideals of a Poset, Respectively All Fixed-Cardinality Subtrees of a Tree. Order 31(1):121-135. doi:10.1007/s11083-013-9292-6 (Problem 198, Problem 199)
[Wright1986]
Wright, R. A., Richmond, B., Odlyzko, A., and McKay, B. D. (1986) Constant Time Generation of Free Trees. SIAM Journal on Computing 15(2):540-548. doi:10.1137/0215039 (Problem 358)
[Xiang1997]
Xiang, L. (1997) Grammar-Oriented Enumeration of Binary Trees. The Computer Journal 40(5):278-291. doi:10.1093/comjnl/40.5.278 (Problem 319)
Yamada, T., Kataoka, S., and Watanabe, K. (2010) Listing All the Minimum Spanning Trees in an Undirected Graph. International Journal of Computer Mathematics 87(14):3175-3185. doi:10.1080/00207160903329699 (Problem 214)
[Yamanaka2006]
Yamanaka, K. and Nakano, S. (2006) Generating all realizers. Electronics and Communications in Japan (Part II: Electronics) 89(7):40-47. doi:10.1002/ecjb.20276 (Problem 175)
[Yamanaka2007]
Yamanaka, K., Kawano, S., Kikuchi, Y., and Nakano, S. (2007) Constant time generation of integer partitions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E90-A(5):888-895. doi:10.1093/ietfec/e90-a.5.888 (Problem 164)
[Yamanaka2009]
Yamanaka, K. and Nakano, S. (2009) Listing All Plane Graphs. Journal of Graph Algorithms and Applications 13(1):5-18. doi:10.7155/jgaa.00174 (Problem 17, Problem 18)
[Yamanaka2009a]
Yamanaka, K., Otachi, Y., and Nakano, S. (2009) Efficient Enumeration of Ordered Trees with k Leaves. In: Das, S. and Uehara, R. (eds.) WALCOM 2009: the 3rd International Workshop on Algorithms and Computation, Kolkata, India, Feb. 2009. Lecture Notes in Computer Science, vol 5431. Springer Berlin Heidelberg, p 141-150. doi:10.1007/978-3-642-00202-1_13 (Problem 163)
[Yamanaka2010]
Yamanaka, K., Nakano, S., Matsui, Y., Uehara, R., and Nakada, K. (2010) Efficient Enumeration of All Ladder Lotteries and Its Application. Theoretical Computer Science 411(16-18):1714-1722. doi:10.1016/j.tcs.2010.01.002 (Problem 44)
[Yamanaka2014]
Yamanaka, K. and Nakano, S. (2014) Efficient Enumeration of All Ladder Lotteries with k Bars. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E97.A(6):1163-1170. doi:10.1587/transfun.E97.A.1163 (Problem 169)
[Yasuko1994]
Yasuko, Y. and Matsui, T. (1994) Finding All the Edge Colorings in Bipartite Graphs （in Japanese, 2部グラフの辺彩色の列挙解法）. 電気学会論文誌. C, 電子・情報・システム部門誌 114(4):444-449 (Problem 122)
[Yau1967]
Yau, S. (1967) Generation of all Hamiltonian Circuits, Paths, and Centers of a Graph, and Related Problems. IEEE Transactions on Circuit Theory 14(1):79-81. doi:10.1109/TCT.1967.1082662 (Problem 417, Problem 418, Problem 419, Problem 433, Problem 434)
[Yeh2010]
Yeh, L. P., Wang, B. F., and Su, H. H. (2010) Efficient algorithms for the problems of enumerating cuts by non-decreasing weights. Algorithmica 56(3):297-312. doi:10.1007/s00453-009-9284-5 (Problem 186, Problem 187)
[Yen1971]
Yen, J. Y. (1971) Finding the K Shortest Loopless Paths in a Network. Management Science 17(11):712-716. doi:10.1287/mnsc.17.11.712 (Problem 121)
[Zaks1979]
Zaks, S. and Richards, D. (1979) Generating Trees and Other Combinatorial Objects Lexicographically. SIAM Journal on Computing 8(1):73-81. doi:10.1137/0208006 (Problem 398)
[Zaks1980]
Zaks, S. (1980) Lexicographic generation of ordered trees. Theoretical Computer Science 10(1):63-82. doi:10.1016/0304-3975(80)90073-0 (Problem 385)
[Zaks1982]
Zaks, S. (1982) Generation and ranking of K-ary trees. Information Processing Letters 14(1):44-48. doi:10.1016/0020-0190(82)90140-5 (Problem 375)
[Zerling1985]
Zerling, D. (1985) Generating Binary Trees Using Rotations. Journal of the ACM 32(3):694-701. doi:10.1145/3828.214141 (Problem 359)
[Zhuang2010]
Zhuang, B. and Nagamochi, H. (2010) Listing triconnected rooted plane graphs. In: Wu, W. and Daescu, O. (eds.) COCOA 2010: the 4th International Conference on Combinatorial Optimization and Applications, Kailua-Kona, HI, USA, Dec. 2010. Lecture Notes in Computer Science, vol 6509. Springer Berlin Heidelberg, p 347-361. doi:10.1007/978-3-642-17461-2_28 (Problem 208, Problem 209)
[Zhuang2010a]
Zhuang, B. and Nagamochi, H. (2010) Generating Internally Triconnected rooted plane graphs. In: Kratochv\'{\i}l, J., Li, A., Fiala, J.ř., and Kolman, P. (eds.) TAMC 2010: the 7th Annual Conference on Theory and Applications of Models of Computation, Prague, Czech Republic, Jun. 2010. Lecture Notes in Computer Science, vol 6108. Springer Berlin Heidelberg, p 467-478. doi:10.1007/978-3-642-13562-0_42 (Problem 219, Problem 220)
[Zhuang2010b]
Zhuang, B. and Nagamochi, H. (2010) Enumerating rooted graphs with reflectional block structures. In: Calamoneri, T. and Diaz, J. (eds.) CIAC 2010: the 7th International Conference on Algorithms and Complexity, Rome, Italy, May. 2010. Lecture Notes in Computer Science, vol 6078. Springer Berlin Heidelberg, p 49-60. doi:10.1007/978-3-642-13073-1_6 (Problem 221)
[Zhuang2010c]
Zhuang, B. and Nagamochi, H. (2010) Constant Time Generation of Biconnected Rooted Plane Graphs. In: Lee, D.-T., Chen, D. Z., and Ying, S. (eds.) FAW 2010: the 4th International Workshop on Frontiers in Algorithmics, Wuhan, China, Aug. 2010. Lecture Notes in Computer Science, vol 6213. Springer Berlin Heidelberg, p 113-123. doi:10.1007/978-3-642-14553-7_13 (Problem 215, Problem 216, Problem 217)
[久田松12]

Last update: 2015-11-03T23:46:57+0900 (JST) by Kunihiro Wasa, XML data and Bibtex data

Keywords: enumeration, listing, counting, polynomial delay algorithm, constant delay algorithm, constant amortized time (CAT) algorithm, incremental polynomial, output polynomial, exponential algorithm, graph, hypergraph, string, geometry, reverse search, best $k$ solutions