Reverse search for enumeration. (English) Zbl 0854.68070

Summary: The reverse search technique has been recently introduced by the authors for efficient enumeration of vertices of polyhedra and arrangements. In this paper, we develop this idea in a general framework and show its broader applications to various problems in operations research, combinatorics, and geometry. In particular, we propose new algorithms for listing (i) all triangulations of a set of \(n\) points in the plane, (ii) all cells in a hyperplane arrangement in \(R^d\), (iii) all spanning trees of a graph, (iv) all Euclidean (noncrossing) trees spanning a set of \(n\) points in the plane, (v) all connected induced subgraphs of a graph, and (vi) all topological orderings of an acyclic graph. Finally, we propose a new algorithm for the 0-1 integer programming problem which can be considered as an alternative to the branch-and-bound algorithm.


68R10 Graph theory (including graph drawing) in computer science
05C30 Enumeration in graph theory
05C05 Trees
Full Text: DOI


[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., Data Structures and Algorithms (1987), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0307.68053
[2] Avis, D., A C implementation of the reverse search vertex enumeration algorithm, (Research Report RIMS Kokyuroku 872 (1994), Kyoto University) · Zbl 0939.68883
[3] Avis, D.; Chvátal, V., Notes on Bland’s pivoting rule, Math. Programming, 8, 24-34 (1978) · Zbl 0403.65025
[4] Avis, D.; Fukuda, K., A basis enumeration algorithm for linear systems with geometric applications, Appl. Math. Lett., 5, 39-42 (1991) · Zbl 0736.90059
[5] Avis, D.; Fukuda, K., A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Discrete Comput. Geom., 8, 295-313 (1992) · Zbl 0752.68082
[6] Buck, R. C., Partien of space, Amer. Math. Monthly, 50, 541-544 (1943) · Zbl 0061.30609
[7] Edelsbrunner, H., Algorithms in Combinatorial Geometry (1987), Springer: Springer Berlin · Zbl 0634.52001
[8] Fortune, S., A note on Delaunay diagonal flips (1987), AT&T Bell Laboratories: AT&T Bell Laboratories Murray Hill, NJ
[9] Fujishige, S., Submodular Functions and Optimization, (Annals of Discrete Mathematics, 47 (1991), North-Holland: North-Holland Amsterdam) · Zbl 1119.90044
[10] Fukuda, K.; Mizukoshi, I., Mathematica package: Vertex enumeration for convex polyhedra and hyperplane arrangements (1991), Graduate School of Systems Management, University of Tsukuba: Graduate School of Systems Management, University of Tsukuba Tokyo, available via anonymous ftp from cs.sunysb.edu (directory pub/Combinatorica)
[11] Fukuda, K.; Saito, K.; Tarawa, A., Combinatorical face enumeration in arrangements and oriented matroids, Discrete Appl. Math., 31, 141-149 (1991) · Zbl 0752.05016
[12] Fukuda, K.; Saito, K.; Tamura, A.; Tokuyama, T., Bounding the number of \(k\)-faces in arrangements of hyperplanes, Discrete Appl. Math., 31, 151-165 (1991) · Zbl 0742.52012
[13] Guibas, L. J.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Trans. Graphics, 4, 74-123 (1985) · Zbl 0586.68059
[14] Knuth, D. E.; Szwarcfiter, J. L., A structured program to generate all topological sorting arrangements, Inform. Process. Lett., 2, 153-157 (1974) · Zbl 0276.68026
[15] Matsui, T., Algorithms for finding all the spanning trees in undirected graphs, (METR93-08 (1993), Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo) · Zbl 0879.68084
[16] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization (1982), Printice-Hall: Printice-Hall Englewood Cliffs, NJ · Zbl 0503.90060
[18] Read, R. C.; Tarjan, R. E., Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 237-252 (1975) · Zbl 0316.05125
[19] Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley New York · Zbl 0665.90063
[20] Shioura, A.; Tamura, A., Efficiently scanning all spanning trees of an undirected graph, J. Oper. Res. Soc. Japan, 38 (1995) · Zbl 0862.90124
[21] Telley, H., Static and dynamic weighted Delaunay triangulations in the Euclidean plane and in the flat torus, (Research Report No. UIUCDCS-R-90-1662 (1990), Department of Computer Science, University of Illinois at Urbana-Champaign)
[22] Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press New York · Zbl 0343.05002
[23] Yao, F. F., On the priority approach to hidden surface algorithms, (Proceedings 21st Symposium on Foundations of Computer Science (1980)), 301-307
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.