Name
Abstract | ||
|---|---|---|
The rotator graph has vertices labeled by the permutations of n in one line notation, and there is an arc from u to v if a prefix of u's label can be rotated to obtain v's label. In other words, it is the directed Cayley graph whose generators are $\sigma_{k} := (1 \ 2 \ \cdots \ k)$ for 2≤k≤n and these rotations are applied to the indices of a permutation. In a restricted rotator graph the allowable rotations are restricted from k∈{2,3,…,n} to k∈G for some smaller (finite) set G⊆{2,3,…,n}. We construct Hamilton cycles for G={n−1,n} and G={2,3,n}, and provide efficient iterative algorithms for generating them. Our results start with a Hamilton cycle in the rotator graph due to Corbett (IEEE Transactions on Parallel and Distributed Systems 3 (1992) 622–626) and are constructed entirely from two sequence operations we name ‘reusing' and ‘recycling'. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-25011-8_26 | IWOCA |
Keywords | Field | DocType |
efficient iterative algorithm,allowable rotation,ieee transactions,cayley graph,line notation,hamilton cycle,rotator graph,sequence operation,restricted rotator graph | Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian path,Permutation,Cayley graph,Prefix,Line notation,Gray code,Sigma,Mathematics | Conference |
Volume | ISSN | Citations |
7056 | 0302-9743 | 2 |
PageRank | References | Authors |
0.42 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brett Stevens | 1 | 30 | 6.68 |
| Aaron Williams | 2 | 139 | 20.42 |