Name
Abstract | ||
|---|---|---|
We show how to construct an explicit Hamilton cycle in the directed Cayley graph ¡¡! Cay(fæn;æn¡1g :Sn), where æk is the rotation (1 2 ¢¢¢ k). The existence of such cycles was shown by Jackson (Discrete Mathematics, 149 (1996) 123{129) but the proof only shows that a certain directed graph is Eulerian, and Knuth (Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)) asks for an explicit construction. We show that a simple recursion describes our Hamilton cycle and that the cycle can be generated by an iterative algorithm that uses O(n) space. Moreover, the algorithm produces each successive edge of the cycle in constant time; such algorithms are said to be loopless. Finally, our Hamilton cycle can be used to construct an explicit universal cycle for the (n ¡ 1)-permutations of a n-set, or as the basis of an e-cient algorithm for generating every n-permutation of an n-set within a circular array or linked list. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1798596.1798598 | ACM Transactions on Algorithms (TALG) |
Keywords | DocType | Volume |
explicit construction,universal cycle,explicit hamilton cycle,loopless algorithm,simple recursion,cayley graph,explicit universal cycle,constant time,hamilton cycle,iterative algorithm,efficient algorithm,circular array,directed graph,discrete mathematics | Journal | 6 |
Issue | ISSN | Citations |
3 | 1549-6325 | 14 |
PageRank | References | Authors |
0.87 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frank Ruskey | 1 | 906 | 116.61 |
| Aaron Williams | 2 | 139 | 20.42 |