Reverse search for enumeration. (English) Zbl 0854.68070

Avis, David; Fukuda, Komei

Discrete Appl. Math. 65, No. 1-3, 21-46 (1996).

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.

MSC:

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

Keywords:

reverse search technique

Software:

Mathematica; PWTri; VertexEnumeration

References:

[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