Abstract
We study an n-dimensional directed symmetric hypercube H n , in which every pair of adjacent vertices is connected by two arcs of opposite directions. Using the computer, we show that for H 4 and for any permutation on its vertices, there exists a system of pairwise arc-disjoint directed paths from each vertex to its target in the permutation. This gives the answer to Szymanski’s conjecture [Szy89] for dimension 4. In addition to this study, we consider in H n the so-called 2-1 routing requests, that is routing requests where any vertex of H n can be used twice as a source, but only once as a target. We give two such routing requests which cannot be routed in H 3. Moreover, we show that for any dimension n ≥ 3, it is possible to find a 2-1 routing request gn such that gn cannot be routed in H n : in other words, for any n ≥ 3, H n is not (2-1)-rearrangeable.
This work has been supported by the Barrande Cooperative Research Grant #97137
Supported by Grant #201/98/1451 of GACR
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
R. Boppana and C.S. Raghavendra. Optimal self-routing of linear-complement permutations in hypercubes. In DISTMEMCC: 5th Distributed Memory Computing Conference, pages 800–808. IEEE Computer Society Press, 1990. 181
S.B. Choi and A.K. Somani. Rearrangeable circuit-switched hypercube architectures for routing permutations. Journal of Parallel and Distributed Computing, 19:125–130, 1993. 181
A. Darmet. Private communication, 1992. 180
Q-P Gu and H. Tamaki. Routing a permutation in the hypercube by two sets of edge disjoint paths. Journal of Parallel and Distributed Computing, 44(2):147–152, 1997. 179, 181, 181
A. Lubiw. Counterexample to a conjecture of Szymanski on hypercube routing. Information Processing Letters, 35:57–61, 1990. 180
A.P. Sprague and H. Tamaki. Routing for involutions of a hypercube. Discrete Applied Mathematics, 48:175–186, 1994. 181
T. Szymanski. On the permutation capability of a circuit-switched hypercube. In Proc. Internat. Conf. on Parallel Processing, pages I-103–I-110, 1989. 179, 180, 180, 190
K. Zemoudeh and A. Sengupta. Routing frequently used bijections on hypercube. In DISTMEMCC: 5th Distributed Memory Computing Conference, pages 824–832. IEEE Computer Society Press, 1990.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baudon, O., Fertin, G., Havel, I. (1999). Routing Permutations in the Hypercube. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds) Graph-Theoretic Concepts in Computer Science. WG 1999. Lecture Notes in Computer Science, vol 1665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46784-X_19
Download citation
DOI: https://doi.org/10.1007/3-540-46784-X_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66731-5
Online ISBN: 978-3-540-46784-7
eBook Packages: Springer Book Archive