Bioch and Ibaraki implemented reverse search to enumerate non-dominated coteries, subsets such that each pair has an element in common. Non-dominated coteries map one-to-one to self-dual binary functions; they define an operator ρ on functions to transform one function into another. Reverse search uses this transformation to enumerate all ND coteries.

Bioch, J.C. and Ibaraki, T. 1994. Generating and Approximating Non-Dominated Coteries. *Rutcor Research Report* RRR 41-94 (December): ps

Show abstract

Bioch, J.C. and Ibaraki, T. 1995. Generating and Approximating Nondominated Coteries. *IEEE Transactions on Parallel and Distributed Systems* 6, no. 9 (September): 905–914. doi

Show abstract

Makino and Kameda implemented reverse search to enumerate regular
non-dominated coteries. Although this is a subset of all coteries, it
eliminates the need to check for equivalence under permutation. As with
Bioch and Ibaraki, coteries are represented by binary functions. They
defined the operator σ to transform functions, creating a search tree
rooted at ƒ = x_{1}.

Makino, K. and Kameda, T. 1999. Transformations on regular nondominated coteries. *DIMACS Technical Report* 99-41 (July). ftp

Show abstract

Makino, K. and Kameda, T. 2001. "Transformations on regular nondominated coteries and their applications" *SIAM Journal on Discrete Mathematics* 14, no. 3: 381–407. doi

Show abstract

Milowski implemented reverse search to find the decomposition of monomial ideals. The ideal is adjusted to be generic and Artinian, then the ideal defines the Scarf complex, a simplex where vertices are minimal generators and facets are their least common multiples. Each facet is a component in the irreducible irredundant decomposition. Facets are enumerated, and the resulting monomials are adjusted back to the original monomial. The algorithm is implemented in the package Monos.

Milowski, R.A. 2004. Computing irredundant irreducible decompositions of large scale monomial ideals. In *Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation*. New York: ACM: 235–242. doi

Show abstract

Ruskey *et al.*
implemented reverse search to enumerate degree sequences in graphs. The
reverse search tree is rooted at the degree sequence of the graph with
one vertex (0), child degree sequences are created by adding to the
sequence and incrementing some of the values. A Pascal implementation
is provided in the paper, and the algorithm is implemented on the Combinatorial Objects Server.

Ruskey, F., Eades, P., Cohen, B. and Scott, A. 1994. Alley CATs in Search of Good Homes. *Congressus Numerantium* 102: 97–110.

Show abstract

Rote implemented reverse search to enumerate faces of a convex hull of a given set of points. The implementation works on degenerate convex hulls, where basis enumeration would fail, by pivoting across lower-dimensional facets rather than pivoting over bases.

Rote, G. 1992. Degenerate Convex Hulls in High Dimensions Without Extra Storage. In *Proceedings of the eighth annual symposium on Computational geometry*. New York: ACM: 26–32. doi

Show abstract

Fukuda *et al.*
implemented reverse search to enumerate the faces of the convex hull of
a set of polytopes. The enumeration pivots across ridges of the
extended convex hull, as Rote's implementation for convex hulls.

Fukuda, K., Liebling, T. and Lütolf, C. 2001. Extended convex hull. *Computational Geometry* 20: 13–23. doi

Show abstract

Huber and Thomas implemented reverse search to find the Gröbner fan of a toric ideal. Adjacent Gröbner cones are found by flipping a common facet binomial. The algorithm is implemented in the package TiGERS and CaTS.

Huber, B. and Thomas, R.R. 2000. Computing Gröbner Fans of Toric Ideals. *Experimental Mathematics* 9, no. 3: 321–331.

Show abstract

Fukuda *et al.*
extend the work of Huber and Thomas to make an algorithm to enumerate
Gröbner fan of an arbitrary polynomial ideal. The algorithm is
implemented in the package gfan.

Fukuda, K., Jensen, A. and Thomas, R.R. 2007. Computing Gröbner Fans. *Mathematics of Computation* 76: 2189–2212. arXiv:math/0509544v1

Show abstract

Sleumer improved on the reverse search method for enumerating cells in a hyperplane arrangement of Avis and Fukuda, by implementing the adjacency oracle and parent function with geometric properties. A unique point in each cell is determined by solving a linear program in each cell; by following the line from the point in each cell to the point in the root cell, the first cell encountered is the parent. Adjacency is determined by a similar geometric approach.

Sleumer, N. 1998. Output-Sensitive Enumeration of Hyperplane Arrangements. In *Algorithm Theory - SWAT'98*,
edited by S. Arnborg and L. Ivansson. Lecture Notes in Computer
Science, vol. 1432. Berlin/Heidelberg: Springer-Verlag: 300–309. doi

Show abstract

Avis *et al.*
implemented reverse search to enumerate non-crossing minimally rigid
edge sets on a set of points (Laman frameworks). Based on the
implementation of Bereg for enumerating pointed pseudotriangulations,
Laman frameworks are connected by flips, the removal of one edge and
the addition of another. The algorithm was revised to enumerate Laman
frameworks constrained to always contain a set of edges, reducing the
number of frameworks on large point sets.

From the enumeration of constrained Laman frameworks, Ohsaki *et al.* enumerated bistable mechanisms, ie those with two self-equilibra states.

Avis, D., Katoh, N., Ohsaki, M., Streinu, I. and Tanigawa, S. 2006. Enumerating Non-crossing Minimally Rigid Frameworks. In *Computing and Combinatorics*. Lecture Notes in Computer Science, vol. 4112: 205–215 doi

Show abstract

Avis, D., Katoh, N., Ohsaki, M., Streinu, I. and Tanigawa, S. 2007. Enumerating Non-crossing Minimally Rigid Frameworks. *Graphs and Combinatorics* 23, suppl. 1 (June): 117-134. doi

Show abstract

Avis, D., Katoh, N., Ohsaki, M., Streinu, I. and Tanigawa, S. 2007.
Enumerating Constrained Non-crossing Minimally Rigid Frameworks. *Discrete and Computational Geometry* Published online (September): doi arXiv:math/0608102v2

Show abstract

Ohsaki, M., Katoh, N., Kinoshita, T., Tanigawa, S., Avis, D. and
Streinu, I. 2008. Enumeration of optimal pin-jointed bistable compliant
mechanisms with non-crossing memebers. *Structural and Multidisciplinary Optimization* Published Online (April): doi

Show abstract

Using the boundary-edge code, Caporossi and Hansen enumerated nonisomorphic planar simply connected polyhexes. A polyhex, or benzenoid system, is a molecule composed of regular hexagons, where two hexagons are disjoint or share exactly one edge. The implementation of reverse search enumerated polyhexes with h ≤ 21 hexagons. Adjacency is defined between two polyhexes by the addition or deletion of a hexagon, and can be determined by manipulating the code string.

Caporossi, G. and Hansen, P. 1998. Enumeration of polyhex hydrocarbons to h=21. *Journal of Chemical Information and Computer Sciences* 38, 610–619. doi

Show abstract

Aringhieri *et al.*
introduced two implementations of reverse search to enumerate alkanes,
chemical compounds with identical weight and molecular formulae, but
different structures. Alkanes can be expressed as trees with degree
constraints, and were encoded using the N-*Tuple* and Centered N-*Tuple*
codes. Two algorithms, one using each code, were implemented. Adjacency
is defined between two trees by the addition or deletion of a leaf and
the edge connecting it. Executables are available online.

Aringhieri, R., Hansen, P. and Malucelli, F. 2003. Chemical trees enumeration algorithms. *Quarterly Journal for the Belgian, French and Italian Operations Research Societies* 1, no. 1 (March): 67–83. doi

Show abstract

Filippi implemented reverse search to find the neighboring vertices of a vertex on a polyhedron. Adjacent vertices are found by lexicographical pivoting.

Filippi, C. 1999. A reverse search algorithm for the neighborhood problem. *Operations Research Letters* 25: 33–37. doi

Show abstract

Balas *et al.*
propose a heuristic for solving 0-1 programming problems, by solving a
neighborhood enumeration problem. First, a fractional solution *x* is found. From *x*, a half-line is constructed and the *k* facets of an octahedron containing *x* and intersecting the half-line are enumerated, by reverse search. An implementation can be found at SCIP (Solving Constraint Integer Programs) under heur_octane.c.

0/1 programs fall into the class of linear programs with an additional reverse convex constraint (LPARC). An algorithm using reverse search for solving the more general class has also been presented, see Kuno and Shigirgo.

Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G. 2001. OCTANE: A new heuristic for pure 0-1 programs. *Operations Research* 49, no. 2 (March-April): 207–225. doi

Show abstract

Finschi and Fukuda used reverse search as part of an algorithm for generating oriented matroids. Oriented matroids are reprsented by tope graphs. By generating particular signatures (assignment of −, 0 or + to vertices) on the tope graph of a matroid, the tope graphs of matroids created by extension can be found. Reverse search is rooted at the signature of all 0s. Adjacency is determined by changing the signature to keep the subgraph of vertices with − assignments connected.

From the collection of oriented matroids, enumeration of hyperplane arrangements and point configurations is possible. These are presented in an online catalog.

For related algorithms on graphs, see subgraphs and data mining.

Finschi, L., and Fukuda, K. 2002. Generation of Oriented Matroids—A Graph Theoretical Approach. *Discrete and Computational Geoemetry* 27: 11–136. doi

Show abstract

Finschi, L., and Fukuda, K. 2003. Complete Combinatorial Generation of
Small Point Configuration and Hyperplane Arrangements. In *Discrete and Computational Geometry: The Goodman-Pollack Festschrift*, edited by B. Aronov, S. Basu, J. Pach, M. Sharir. Algorithms and Combinatorics, vol 25. Springer-Verlag: 425–440.

Show abstract

Dumitrescu *et al.*
implemented reverse search to enumerate triangulation paths, paths
which are a particular intersection of a line segment in a polygon and
its triangulation. Adjacency is determined by flips in the
triangulation, with the search tree rooted at path in the Delauney
triangulation.

Dumitrescu, A., Gärtner, B., Pedroni, S. and Welzl, E. 2001. Enumerating triangulation paths. *Computational Geometry* 20: 3–12. doi

Show abstract

Avis and Kaluzny impelemented reverse search as part of a program to enumerate monotone vertex disjoint paths of a linear program. The program uses reverse search to enumerate bases for degenerate vertices within the path finding algorithm. The program, DisjointLP, is available online.

Avis, D. and Kaluzny, B. 2005. Computing Disjoint Paths in Linear Programs. *GERAD Technical Report* G-2005-26. (March)

Show abstract

Brim *et al.*
implemented reverse search to make a distributed algorithm to solve the
single-source shortest path problem. The algorithm makes use of reverse
search to traverse the graph, maintaining shortest path distance from
each vertex to the source. A distributed algorithm and the
computational experience solving an LTL verification problem is given.

Brim,
L., Černá, I., Křcál, P., Pelánek, R. How to Employ Reverse Search in
Distributed Single Source Shortest Paths. 2001. In *SOFSEM 2001: Theory and Practice of Informatics*. Lecture Notes in Computer Science, vol. 2234: 191–200. doi

Show abstract

Andrzejak and Fukuda used reverse search to enumerate *k*-sets of a given point set. Two approaches are given. In one, reverse search enumerates *k*-sets from the *k*-set polytope, a polytope constructed with a bijection from vertices of the polytope to *k*-sets; reverse search is implemented to enumerate these vertices. In the other implementation, *k*-sets
are enumerated by using combinatorial flips, trading one element of the
subset for another not in the subset. Such sets are then tested to
actually be *k*-sets by solving a linear program.

Andrzejak, A. and Fukuda, K. 1999. Optimization over k-set Polytopes and Efficient k-set Enumeration. In *Algorithms and Data Structures*. Lecture Notes in Computer Science, vol. 1663: 772–783. doi

Show abstract

Andrzejak, A. 2000. On k-sets and their Generalizations. PhD diss., ETH Zurich.

Show abstract

Ackerman *et al.*
(2006) implemented reverse search to enumerate the number of
rectangulations of a rectangle with n points. The reverse search tree
is rooted at the rectangulation with all segments horizontal, and edges
are determined by flips (changing a horizontal segment to vertical) and
rotates (operations at an intersection of two segments, extending one
segment past the other and shortening the other to the intersection
point).

Ackerman, E., Barequet, G. and Pinter, RY. 2006. On the number of rectangulations of a planar point set. *Journal of Combinatorial Theory* Series A 113: 1027–1091. doi

Show abstract

Ackerman, E. 2006. Counting problems for geometric structures: rectangulations, floorplans, and quasi-planar graphs. PhD diss., Technion-Isreal Institute of Technology, Haifa.

Show abstract

Elmaghraby and Thoney implement reverse search to enumerate schedules of jobs on a two-machine workflow, where the processing times of jobs are random variables. Optimum schedule(s), determined by the expected value of the processing time, root the search tree(s). Permutations are pivoted according to the positions of the jobs in the optimum schedule.

Elmaghraby, S. and Thoney, K. 1999. The two-machine stochastic flowshop problem with arbitrary processing time distribution. *IIE Transactions* 31: 467–477. doi

Show abstract

Moriyama and Hachimori implemented reverse search to determine whether
or not a given simplical complex is shellable. The algorithm depends on
finding an *h*-assignment to the facets to determine shellability. Partial *h*-assignments are generated by reverse search; the parent of a (partial) *h*-assignment
is found by reducing the assignment from the facet with the largest
index, for some indexing. The algorithm is implemented in the program rsshell.

S. Moriyama and M. Hachimori, *h*-Assignments of simplical complexes and reverse search, Discrete Applied Mathematics 154 (2006) 594-597. doi

Show abstract

Eppstein implemented reverse search to enumerate maximal independent sets of a graph. Vertices are ordered; the search tree is rooted at the lexicographically first maximal independent set. A dynamic data structure is used to test dominated vertices in the graph, used in the search to test for maximality.

Eppstein, D. 2005. All maximal independent sets and dynamic dominance for sparse graphs. In *SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms*. Philadelpha: Society for Industrial and Applied Mathematics. 451–459. arXiv:cs/0407036v1

Show abstract

Kiyomi and Uno implemented reverse search to enumerate chordal subgraphs. The search tree is rooted at single vertices, child subgraphs are generated by adding cliques.

Kiyomi, M. and Uno, T. 2006. Generating Chordal Graphs Included in Given Graphs. *IEICE - Transactions on Information and Systems* E98-D, no. 2 (February): 763–770. doi

Show abstract

Kiyomi *et al.*
implemented reverse search to enumerate chordal supergraphs, interval
supergraphs, and interval subgraphs. The reverse search tree, for all
enumerations, is traversed by adding or removing an edge, and is rooted
at K_{n}, for supergraph enumerations, or the empty graph, for subgraph enumerations.

Kiyomi, M., Kijima, S. and Uno, T. 2006. Listing Chordal and Interval Graphs. In *Graph-Theoretic Concepts in Computer Science*. Lecture Notes in Computer Science, vol. 4271. Berlin/Heidelberg: Springer: 68–77. doi

Show abstract

Uno implemented reverse search to enumerate pseudo-cliques, subgraphs with edge sets larger than a certain threshold. The reverse search tree is rooted at the empty graph. Adjacency between pseudo-cliques is determined by removal or insertion of a vertex. Algorithm is implemented as PCE.

Uno, T. 2007. An Efficient Algorithm for Enumerating Pseudo Cliques. In *Algorithms and Computation*. Lecture Notes in Computer Science, vol. 4837. Berlin/Heidelberg: Springer: 402–414. doi

Show abstract

Asai *et al.*
implemented reverse search to enumerate frequent ordered and unordered
trees from a database. FREQT, for enumerating ordered trees, and UNOT,
for unordered trees, are available online.

Asai, T., Arimura, H., Uno, T. and Nakano, S. 2003. Discovering Frequent Substructures in Large Unordered Trees. In *Discovery Science*. Lecture Notes in Computer Science, vol. 2843: 47–61. doi

Show abstract

Asai, T.,Arimura, H., Uno, T., Nakano, S. and Satoh, K. 2003. Efficient Tree Mining Using Reverse Search. *DOI Technical Report* 218. Department of Informatics, Kyushu University (June). pdf

Show abstract

An attribute tree is a subclass of ordered labelled trees, where the children of each node are distinct. Arimura and Uno proposed an implementation of reverse search to enumerate frequent closed patterns in attribute trees, by using prefix-preserving closure expansion to find children in the reverse search tree.

Arimura, H. and Uno, T. 2005. An Output-Polynomial Time Algorithm for Mining Frequent Closed Attribute Trees. In *Inductive Logic Programming*. Lecture Notes in Computer Science, vol. 3625: 1–9. doi

Show abstract

Uno and Arimura implemented reverse search to enumerate pseudo frequent
itemsets from a database of transactions, where a transaction *T* is included in the occurences of a pattern *P* if |*P*\*T*| ≤ *k*, for some constant *k*.

Uno, T. and Arimura, H. 2007. An Efficient Polynomial Delay Algorithm for Pseudo Frequent Itemset Mining. In *Inductive Logic Programming*. Lecture Notes in Computer Science, vol. 4755: 219–230. doi

Show abstract

Arimura and Uno implemented reverse search to enumerate maximal flexible patterns, sequences of letters from an alphabet and wildcard symbols. Patterns are generated by reverse search, then checked for frequency above a threshold. Child patterns are expanded by concatenating a letter or a letter and a wildcard symbol, then its maximality is checked.

Arimura, H. and Uno, T. 2008. Mining Maximal Flexible Patterns in a Sequence. In *New Frontiers in Artificial Intelligence*. Lectures Notes in Computer Science, vol. 4914: 307–317. doi

Show abstract

Uno revised a method for enumerating maximal matchings by Tsukiyama *et al.* to improve running time to *O*(|*E*|+|*V*|+Δ*N*)
for finding maximal matchings in non-bipartite graphs. The reverse
search tree is rooted at the matching of the subgraph with only one
edge; child matchings are maximal matching with an added edge. Leaves
of the search tree are maximal matchings of the entire graph.

Uno, T. 2001. A Fast Algorithm for Enumerating Non-Bipartite Maximal Matchings. *National Institute Informatics Journal* 3: 89–97.

Show abstract

Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I. 1977. A New Algorithm for Generating All the Maximal Independent Sets. *SIAM Journal on Computing* 6, iss. 3: 505–517. doi

Show abstract

Trombettoni and Wilczkowiak simplified reverse search to find subgraphs of a graph modelling a 3-D scene from 2-D pictures. Subgraphs are matched to known patterns for rendering the scene. The child subgraph is created by adding a connected vertex and its edge to a subgraph. Search depth is limited by the largest subgraph in the dictionary of patterns against which subgraphs are matched.

Wilczkowiak, M. 2004. 3D Modelling From Images Using Geometric Constraints. PhD diss., Institut National Polytechnique de Grenoble.

Show abstract

Trombettoni, G. and Wilczkowiak, M. 2003. Scene reconstruction based on
constraints: Details on the equation system decomposition. In *Principles and Practice of Constraint Programming - Cp 2003, Proceedings*. Lecture Notes in Computer Science, vol. 2833: 956–961. doi

Show abstract

Trombettoni, G. and Wilczkowiak, M. 2006. GPDOF - A fast algorithm to
decompose under-constrained geometric constraint systems: Application
to 3D modeling. *International Journal of Computational Geometry & Applications* 16, Nos. 5 & 6. 479–511. doi

Show abstract

A geometric graph, or geograph, is an edge- and vertex-labelled graph
representing a geometric system. Vertices have coordinates; edges
represent geometric relations. Arimura *et al.* implemented reverse search to enumerate maximal patterns (subgraphs) in a given geometric graph with certain frequency.

Arimura, H., Uno T. and Shimozono, S. 2007. Time and Space Efficient Discovery of Maximal Geometric Graphs. In *Discovery Science*. Lecture Notes in Computer Science, vol. 4755: 42–55. doi

Show abstract

Ge *et al.*
implemented reverse search to find periodic behavior, or T-invariants,
of Petri nets. The Petri net is expressed as an incidince matrix from
the edge weights; the incidence matrix creates the constraints for a
linear program formulation. Feasible solutions to the linear program
are equivalent to T-invariants. Feasible solutions are connected by
pivoting operations.

Ge, Q-W., Fukunaga, T. and Nakata, M. 2005. On Generating Elementary T-invariants of Petri Nets by Linear Programming. In *IEEE International Symposium on Circuits and Systems, 2005*: 168–171.

Show abstract

Kurumida *et al.*
implemented reverse search to search scale-free networks with small
space requirements. A spanning forest is defined over the network, with
roots at vertices with degree greater than its neighbors. The algorithm
uses only local information, and has small space requirements.

Kurumida, Y., Ono, H., Sadakane, K. and Yamashita, M. 2006. Forest
Search: A Paradigm for Faster Exploration of Scale-Free Networks. In *Parallel and Distributed Processing and Applications*. Lecture Notes in Computer Science, vol. 4330: 39–50. doi

Show abstract

De Berg *et al.*
implemented reverse search to traverse a subdivision (eg, of GIS data)
that does not require mark bits or extra storage. The starting cell and
a point within that cell is chosen arbitrarily; the incident edge of an
adjacent cells is determined by the edge closest to the chosen point in
the starting cell.

de Berg, M., van Oostrum, R. and Overmars, M. 1996. Simple traversal of a subdivision without extra storage. In *SCG '96: Proceedings of the twelfth annual symposium on Computational geometry* New York: ACM: 405–406. doi

Show abstract

Bose and Morin revised the traversal by de Berg to use a 4-tuple key for each edge to determine an order on the edges; the lexicographically minimal edge for a face is chosen as the edge incident to the parent cell. This traversal was also implemented as a routing algorithm.

Bose, P. and Morin, P. 2000. An Improved Algorithm for Subdivision Traversal without Extra Storage. In *Algorithms and Computation*. Lecture Notes in Computer Science, vol. 1969: 47–104. doi

Show abstract

Morin, P. 2001. Online Routing in Geometric Graphs. PhD diss., Carlton University, Ottawa.

Show abstract

Chávez *et al.*,
expanding on the traversals by de Berg and Bose, implemented reverse
search to traverse a quasi-planar subdivision, where a subset of the
edges are allowed to cross. A 5-tuple key is defined on the edges,
lexicographical ordering of the keys defines the entry edge for each
quasi-face.

Chávez,
E., Dobrev, S., Kranakis, E., Opatrny, J., Stacho, L. and Urrutia, J.
2004. Traversal of a Quasi-Planar Subdivision Without Using Mark Bits.
In *Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International*: 217. doi

Show abstract

Eppstein and Falmagne implemented reverse search to enumerate states of a medium, given a black-box description. A medium is a restricted deterministic finite state automata derived from political choice theory, but is shown equivalent to many combinatorial structures. A black-box description of a medium is defined by its set of tokens, a transition function, and a single state. Using reverse search, all the states of a medium can be enumerated given only a black box description. Implementation of the reverse search in Python is included.

Eppstein, D. and Falmagne, J.-C. 2008. Algorithms for media. *Discrete Applied Mathematics* 156: 1308–1320. doi

Show abstract

Shioura, Tamura *et al.*
implemented reverse search to enumerate spanning trees of an undirected
graph. The reverse search tree is rooted at the depth-first spanning
tree, adjacency is determined by flipping edges: trading an edge in the
tree for one not in tree, to maintain a spanning tree. Flips are chosen
by a labelling on the edges. The revised version uses a different data
structure and is space and time optimal. A C implementation of the
optimized version is available, spantree.

Shioura, A. and Tamura, A. 1995. Efficiently Scanning all Spanning Trees of Undirected Graphs. *Journal of the Operations Research Society of Japan* 38, no. 3 (September): 331–344.

Show abstract

Shioura, A., Tamura, A. and Uno, T. 1997. An Optimal Algorithm for Scanning all Spanning Trees of Undirected Graphs. *SIAM Journal of Computing* 26, no. 3 (June): 678–692. doi

Show abstract

Matsui wrote an algorithm for generating all spanning trees which creates a tree of spanning trees which can be traversed by depth-first or breadth-first search. The search tree is rooted at the lexicographically maximum spanning tree. Trees are connected by flips; candidate edges for flips are determined by a labelling of edges done in preprocessing. The algorithm (as a depth first search) is time and space optimal. A modification of the algorithm for graphs with weighted edges outputs the spanning trees in order of rank.

Matsui, T. 1997. A Flexible Algorithm for Generating all the Spanning Trees in Undirected Graphs. *Algorithmica* 18: 530–544. doi

Show abstract

Nievergelt *et al.*
implemented reverse search to enumerate spanning trees constrained by
tree diameter, maximal degree and number of leaves. The algorithm
relies on leaf flips rather than general edge flips. Algorithms are
implemented in the ZRAM library.

Nievergelt, J., Deo, N. and Marzetta, A. 1999. Memory-efficient enumeration of constrained spanning trees. *Information Processing Letters* 72: 47–53. doi

Show abstract

Nievergelt presented adjacency rules to implement reverse search to enumerate the *k* shortest Euclidean spanning trees over a set of points in the plane, or Euclidean spanning trees shorter than a given bound *c*.
The search tree is rooted at the minimum spanning tree. Marzetta and
Nievergelt (2001) present the implementation, with computational
results. Code is available in the ZRAM library.

Nievergelt, J. 2000. Exhaustive Search, Combinatorial Optimization and
Enumeration: Exploring the Potential of Raw Computing Power. In *SOFSEM 2000: Theory and Practice of Informatics*. Lecture Notes in Computer Science, vol. 1963: 87–125. doi

Show abstract

Marzetta A. and Nievergelt, J. 2001. Enumerating the *k* best plane spanning trees. *Computational Geometry* 18: 55–64. doi

Show abstract

Katoh and Tanigawa implement reverse search to enumerate constrained plane spanning trees, building off Bespamiyatnikh's implementation to enumerate triangulations. The search tree is rooted at the smallest indexed spanning tree containing *F*, a non-crossing edge set on the graph. Trees are constrained to all contain *F*.

Katoh, N. and Tanigawa, S. 2007. Enumerating Constrained Non-crossing Geometric Spanning Trees. In *Computing and Combinatorics*. Lectures Notes in Computer Science, vol. 4598: 243–253. doi

Show abstract

Okamoto and Uno implemented reverse search to enumerate spanning trees that minimize the cost according to a set of cost functions on the edges.

Okamoto, Y. and Uno, T. 2007. A Polynomial-Time-Delay and
Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria
Optimization. In *Algorithms and Computation*. Lecture Notes in Computer Science, vol. 4835: 609–620. doi

Show abstract

Filippi and Romanin-Jacur implemented reverse search to enumerate feasible bases of solutions to the multiparametric demand linear transportation problem (MDLTP). MDLTP problems are transporatation problems with fixed supplies and varying demands. By representing sources and destinations in a bipartite graph, spanning trees can be found which represent dual-feasible bases of the problem. Spanning trees are adjacent by flip operations, the replacement of an edge in the tree by an edge not in the tree.

Filippi, C. and Romanin-Jacur, G. 2002. Multiparametric demand transportation problem. *European Journal of Operational Research* 139: 206–219.

Show abstract

Avis enumerated all 2- and 3-connected, rooted, planar triangulations on *n* points, with *r*
points on the outer face. Adjacency is determined between two
triangulations by flipping edges, ie, removing one edge and replacing
it by another so that the graph is still a 2- or 3-connected, rooted,
planar triangulation.

Avis, D. 1996. Generating rooted triangulations without repetitions. *Algorithmica* 16: 618–632. doi

Show abstract

Kong implemented reverse search to enumerate all non-isomorphic rooted triangulations of n points in the plane, with minimum degree four. The reverse search tree is rooted at a special triangulation, the "stand with gem," and adjacency is determined by single flips, and also two simultaneous flips. Computational results are given for n ≤ 17.

Kong, C.M. 1996. Generating Rooted Triangulations with Minimum Degree Four. MSc Thesis, McGill University.

Show abstract

Masada *et al.*
implemented reverse search to enumerate regular triangulations in any
dimension. Triangulations are mapped one-to-one to a weight vector,
which form the vertices of the reverse search tree; flips determine
edges. Regularity of a triangulation is check by solving an associated
linear program. Degenerate and non-degenerate cases are considered; as
are spanning and non-spanning triangulations. An efficient data
structure is provided for manipulation of the triangulations. Imai *et al.*
also includes an implementation of reverse search for enumerating
equivalence classes of regular triangulations. Revised code is available online.

Masada, T., Imai, H. and Imai, K. 1996. Enumeration of regular triangulations. In *SCG '96: Proceedings of the twelfth annual symposium on Compuational geometry*. New York: ACM. 224–233. doi

Show abstract

Masada, T., Imai, K. and Imai, H. 1996. Enumeration of regular triangulations with computational results. *Zeitschrift fur angewandte Mathematik und Mechanik* 76 S. 3: 187–190. doi

Show abstract

Imai, H., Masada, T., Takeuchi, F. and Imai, K. 2002. Enumerating triangulations in general dimensions. *International Journal of Computational Geometry & Applications* 12, no. 6. 455–480. doi

Show abstract

Bespamyatnikh implemented reverse search to enumerate triangulations of *n* points in the plane in general position (2002) and *n* convex points in ℝ^{3}
(2001). Points are labelled in both cases. In the planar case, the edge
set of the triangulation determines a vector; the lexicographically
maximum triangulation roots the reverse search tree. Edges in the
search tree are determined by flips of edges. In the ℝ^{3}
case, rank of a triangulation is assigned by matching a triangulation
to the convex hull of a subset of the points. The reverse search tree
is rooted at the triangulation of rank *n*−3, and edges are determined by bistellar geometric flips. Both algorithms enumerate all triangulations in *O*(log log *n*) time using the van Emde Boas data structure.

This implementation was extended to enumerate constrained spanning trees.

Bespamyatnikh, S. 2001. Enumerating Triangulations of Convex Polytopes. *Discrete Mathematics and Theoretical Computer Science* 4, no. 2: 111–122.

Show abstract

Bespamyatnikh, S. 2002. An efficient algorithm for enumeration of triangulations. *Computational Geometry—Theory and Applications* 23, no. 3: 271–279. doi

Show abstract

Bereg implemented reverse search to enumerate pointed pseudo-triangulations of *n* points in the plane, extending the work on triangulations in the plane and in ℝ^{3}.
The pseudo-triangulation determines a vector by the edges in the convex
hull of a subset of the points which appear in the triangulation and
the number of pseduo-triangles with a vertex at one point in the
subset. The search tree is rooted at the lexico-maximal triangulation.
Flips determine edges in the search tree.

This implementation was used in part for enumerating Laman frameworks.

Bereg, S. 2005 Enumerating pseudo-triangulations in the plane. *Computational Geometry—Theory and Applications* 30, no.: 207–222. doi

Show abstract

Ferrez *et al.*
implemented reverse search to enumerate the extreme points of a
zonotope, in order to solve fixed rank convex quadratic maximization
problems. Reverse search traverses the cells of the dual of the
zonotope, an arrangement of hyperplanes. Adjacency is determined by ray
shooting, ie following the line from a point in the cell to the root
cell, and returning the first cell encountered. This adjacency oracle
requires only solving one linear program, reducing complexity from
previous results. The algorithm was implemented using ZRAM search bench
and cddlib libraries; more details and code can be found in RS_TOPE020713.tar.gz

A similar ray tracing approach to adjacency is used in reverse search implementations of traversals. For a heuristic for solving general 0/1 problems using reverse search, see Balas *et al.*

Ferrez, J.-A., Fukuda, K., and Liebling, Th.M. 2005. Solving the fixed
rank convex quadratic maximization in binary variables by a parallel
zonotope construction algorithm. *European Journal of Operational Research* 166: 35–50. doi

Show abstract

Fukuda implemented reverse search to enumerate the extreme points of the Minkowski sum of a set of polytopes. The adjacency oracle is determined by solving an associated linear program.

Fukuda and Weibel extended the algorithm to enumerate all higher dimensional faces by enumerating for each vertex *v* the faces which have *v* as a sink in an LP orientation. The algorithms has been implemented in the program MINKSUM.

Fukuda, K. 2004. From the zonotope construction to the Minkowski addition of convex polytopes. *Journal of Symbolic Computing* 38: 1261–1272. doi

Show abstract

Fukuda K. and Weibel, C. 2005. Computing All Faces of the Minkowski Sum of V-Polytopes. In *Proceedings of the 17th Canadian Conference on Computational Geometry*: 256–259. pdf

Show abstract

Zhan implemented reverse search to enumerate the vertices of a base polyhedron of a submodular function. The reverse search tree is rooted at a vertex (vector) predefined with the values of the functions on particular sets. Adjacent vertices are found from the Hasse diagram of a vertex defined by the submodular function.

Zhan, P. 1997. A Polynomial Algorithm for Enumerating All Vertices of a Base Polyhedra. *Journal of the Operations Research Society of Japan* 40, no. 3 (September): 329–340.

Show abstract

Kuno and Shiguro implemented reverse search to solve reverse convex
problems, optimization problems where the feasible set is the
difference of two convex sets: let *D* and *C* be the sets such that the feasible set is *D*\*C*, then the proposed algorithm enumerates the vertices of *D*,
searching for an optimal solution to the given program. Included in
this set of problems is the class of linear programs with an additional
reverse convex constraint, including 0/1 integer programs.

Kuno, T. and Shiguro, Y. 2007. A Polynomial-Space Finite Algorithm for Solving a Class of Reverse Convex Programs. *Technical Report, Tsukuba University* CS-TR-07-8. pdf

Show abstract

Fukuda *et al.*
implemented reverse search to solve the problem of vector partitioning,
by enumerating the vertices of the partition polytope. The vector
partitioning problem takes as input a set of vectors and a function on
the sum of vectors in each part. Adjacency between vector partitions is
determined by solving a linear program associated with the particular
vertex (partition).

Fukuda, K., Onn, S. and Rosta, V. 2003. An Adaptive Algorithm for Vector Partitioning. *Journal of Global Optimization* 25: 305–319. doi

Show abstract

Bremner *et al.*
implemented primal-dual reverse search for facet and vertex
enumeration. For some polytopes, it may be easier to enumerate the
vertices (facets) than the facets (vertices). pdReverseSearch uses the
easy enumeration as the oracle for the hard enumeration. The algorithm
is implemented in pd.

Bremner, D., Fukuda, K. and Marzetta, A. 1998. *Discrete and Computational Geometry* 20: 333–357. doi

Show abstract