Combinatorial Algorithms for Listing Paths in Minimal Change Order
Combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we dea
- PDF / 473,492 Bytes
- 19 Pages / 430 x 660 pts Page_size
- 49 Downloads / 198 Views
Department of Computer Science National University of Computer and Emerging Sciences Block B, Faisal Town Lahore, Pakistan [email protected] 2 Center for Advanced Studies in Mathematics Lahore University of Management Sciences Opposite Sector “U”, DHA Lahore, Pakistan [email protected]
Abstract. Combinatorial algorithms that list combinatorial objects in minimal change order are of fundamental interest in computer science and mathematics. In minimal change ordering, successive elements differ in some pre-specified small way. In this paper, we deal with the generation of paths in a special type of minimal change ordering, the revolving door ordering. We propose a simple algorithm to list all paths in a complete graph, Kn , with n vertices in revolving door order such that each path is generated exactly once. The algorithm is built using space and time efficient schemes that list all spanning paths and “path sets” in revolving door order. Our algorithm is optimal in the sense that it operates in constant amortized time (CAT) and uses linear space. Keywords: Combinatorial algorithms, Minimal change order, Revolving door order, Complete graph, Generation of paths.
1
Introduction
Generation of the combinatorial objects is of fundamental interest in computer science. In the last few decades, a tremendous amount of research has been carried out in this area as the emergence of high speed computers has made it possible to construct exhaustive lists of combinatorial objects. We can speed up combinatorial generation by listing objects in minimal change order; an order in which successive elements differ in a small way. Combinatorial algorithms based on minimal change ordering provide new insights into the structure of combinatorial families as they usually involve elegant recursive constructions [8]. The minimal change order in which two consecutive objects have distance two (that is they differ in exactly two positions) is named revolving door order by Nijenhuis and Wilf [1,5]. Much work has been done in listing trees J. Janssen and P. Pralat (Eds.): CAAN 2007, LNCS 4852, pp. 112–130, 2007. c Springer-Verlag Berlin Heidelberg 2007
Combinatorial Algorithms for Listing Paths in Minimal Change Order
113
in revolving door order so that successive trees differ only by an edge. Malcolm Simth [5] proposes a revolving door algorithm for listing all spanning trees in a graph and recently Korsh [6] gives a gray code scheme for generating rooted and free trees. However, we know of no published algorithm that generates all paths in revolving door order in a complete graph, Kn , with n vertices. Finding all paths in a graph is a fundamental aspect in solving scheduling problems, measuring accessibility and traffic flows. In some cases, we can map paths and circuits to some specific class of permutation. This is helpful, since, generation of all permutations is one of the most studied areas in combinatorial generation. Recently, Knuth has compiled comprehensive material on permutation generation in his new volume on combinat
Data Loading...
