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’.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Compton, R.C., Williamson, S.G.: Doubly Adjacent Gray Codes for the Symmetric Group. Linear and Multilinear Algebra 35(3), 237–293 (1993)
Corbett, P.F.: Rotator Graphs: An Efficient Topology for Point-to-Point Multiprocessor Networks. IEEE Transactions on Parallel and Distributed Systems 3, 622–626 (1992)
Corbett, P.F., Scherson, I.D.: Sorting in Mesh Connected Multiprocessors. IEEE Transactions on Parallel and Distributed Systems 3, 626–632 (1992)
Ehrlich, G.: Loopless Algorithms for Generating Permutations, Combinations and Other Combinatorial Configurations. IEEE Transactions on Parallel and Distributed Systems 3, 626–632 (1992); Journal of the ACM 20(3), 500–513 (1973)
Hamada, Y., Bao, F., Mei, A., Igarashi, Y.: Nonadaptive Fault-Tolerant File Transmission in Rotator Graphs. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E79-A 4, 477–482 (1996)
Holroyd, A., Ruskey, F., Williams, A.: Faster Generation of Shorthand Universal Cycles for Permutations. In: Thai, M.T., Sahni, S. (eds.) COCOON 2010. LNCS, vol. 6196, pp. 298–307. Springer, Heidelberg (2010)
Holroyd, A., Ruskey, F., Williams, A.: Shorthand Universal Cycles for Permutations. Algorithmica (to appear)
Knuth, D.E.: The Art of Computer Programming. Generating All Tuples and Permutations, Fascicle 2, vol. 4. Addison-Wesley (2005)
Kuo, C.-J., Hsu, C.-C., Lin, H.-R., Lin, K.-K.: An Efficient Algorithm for Minimum Feedback Vertex Sets in Rotator Graphs. Information Processing Letters 109(9), 450–453 (2009)
Lin, H.-R., Hsu, C.-C.: Topological Properties of Bi-Rotator Graphs. IEICE Transactions on Information and Systems E86-D(10), 2172–2178 (2003)
Ponnuswamy, S., Chaudhary, V.: Embedding of Cycles in Rotator and Incomplete Rotator Graphs. In: Proceedings of the Sixth IEEE Symposium on Parallel and Distributed Processing, October 26-29, pp. 603–610 (1994)
Ruskey, F., Williams, A.: An Explicit Universal Cycle for the (n−1)-Permutations of an n-set. ACM Transactions on Algorithms 6(3), article 45 (2010)
Williams, A.: Loopless Generation of Multiset Permutations Using a Constant Number of Variables by Prefix Shifts. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, pp. 987–996 (2009)
Yasuto, S., Ken’Ichi, K., Mario, N.: Node-Disjoint Paths Problem in a Rotator Graph. Joho Shori Gakkai Shinpojiumu Ronbunshu 14, 93–100 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stevens, B., Williams, A. (2011). Hamilton Cycles in Restricted Rotator Graphs. In: Iliopoulos, C.S., Smyth, W.F. (eds) Combinatorial Algorithms. IWOCA 2011. Lecture Notes in Computer Science, vol 7056. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25011-8_26
Download citation
DOI: https://doi.org/10.1007/978-3-642-25011-8_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25010-1
Online ISBN: 978-3-642-25011-8
eBook Packages: Computer ScienceComputer Science (R0)