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 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, K_n, 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.