Enumeration of Enumeration Algorithms and Its Complexity

The latest version is in arXiv:1605.0510 or github pages.

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.
Reference: [Masada1996]
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.
Reference: [Masada1996]
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.
Reference: [Sawada2002a]

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:
Reference: [Read1975]
P104: Enumeration of all cycles in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All cycles in $G$.
Complexity: $O(|E|)$ time per cycle with $O(|E|)$ space.
Comment:
Reference: [Read1975]
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:
Reference: [Read1975]
P106: Enumeration of all paths in a directed graph
Input: A directed graph $G = (V, E)$.
Output: All paths in $G$.
Complexity: $O(|E|)$ time per path with $O(|E|)$ space.
Comment:
Reference: [Read1975]
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]

Quadrangle

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]

Quadrangulation

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:
Reference: [Read1975]
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.
Comment: Using breadth first manner.
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$.
Reference: [Yamada2010]

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.
Reference: [Dourado2014]

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:
Reference: [Sawada2006]
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:
Reference: [Sawada2006]
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]

Ladder lottery

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.
Reference: [Sawada2001]

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:
Reference: [Sawada2003]

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:
Reference: [Sawada2003a]

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)
[Dourado2014]
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)
[Masada1996]
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)
[Read1975]
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)
[Sawada2001]
Sawada, J. (2001) Generating Bracelets in Constant Amortized Time. SIAM Journal on Computing 31(1):259-268. doi:10.1137/S0097539700377037 (Problem 43)
[Sawada2002a]
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)
[Sawada2003]
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)
[Sawada2003a]
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)
[Sawada2006]
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)
[Yamada2010]
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]
久保幹雄,田村明久,松井 知己 (2012) 応用数理計画ハンドブック(普及版),朝倉書店.(in Japanese)
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