Reverse Search for Enumeration — Implementations

Coteries

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 ƒ = x1.

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

Decomposition of Monomial Ideals

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

Degree sequences

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

Faces of a convex hull

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

Gröbner fans

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

Hyperplane arrangements

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

Laman frameworks and bistable mechanisms

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

Molecules

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

Neighborhood

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

Oriented matroids

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

Paths

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

Point Sets

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

Rectangulations

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

Scheduling

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

Shellability

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

Subgraphs and data mining

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 Kn, 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

T-invariants

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

Traversal and routing

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

Trees

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

Triangulations

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

Vertex enumeration

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