×
Feldmann, Rainer; Mysliwietz, Peter

The shuffle exchange network has a Hamiltonian path. (English) Zbl 1494.68193

Havel, Ivan M. (ed.) et al., Mathematical foundations of computer science 1992. 17th international symposium, Prague, Czechoslovakia, August 24–28, 1992. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 629, 246-254 (1992).
Summary: The problem to determine whether a network contains a Hamiltonian path has been a. fundamental problem in graph theory. We prove the existence of a Hamiltonian path in the Shuffle Exchange network \(\mathrm{SX}(n)\). This problem has been posed as an open problem by F. T. Leighton [Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. San Mateo, CA: Morgan Kaufmann Publishers (1992; Zbl 0743.68007)] and M. R. Samatham and D. K. Pradhan [IEEE Trans. Comput. 38, No. 4, 567–581 (1989; Zbl 0671.94028)].
For the entire collection see [Zbl 1415.68030].

Cited in 1 Review
Cited in 1 Document

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 0743.68007; Zbl 0671.94028
PDF BibTeX XML Cite
\textit{R. Feldmann} and \textit{P. Mysliwietz}, Lect. Notes Comput. Sci. 629, 246--254 (1992; Zbl 1494.68193)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Fred Annexstein, Marc Baumslag, Arnold L. RosenbergGroup Action Graphs and Parallel Architectures. SIAM Journal of Computing, Vol 19, No 3, pp 554-569, (1990) · Zbl 0698.68064
[2] Hans L. BodlaenderThe Classification of Coverings of Processor Networks. Journal of Parallel and Distributed Computing 6, pp 166-182, (1989)
[3] N. G. de BruijnA Combinatorial Problem. Indagationes Math. 8, pp 461-467, (1946) · Zbl 0060.02701
[4] Rainer Feldmann, Walter UngerThe Cube-Connected Cycles Network is a Subgraph of the Butterfly Network. submitted to Parallel Processing Letters, (1991)
[5] Rainer Feldmann, Peter Mysliwietz, Stefan TschökeThe Shuffle Exchange Network of Dimension \(2\) Has a Hamiltonian Path. unpublished manuscript, 1991
[6] E. N. GilbertGray Codes and Paths on the \(n\)-Cube. Bell System Technical Journal 37, pp 815-826, (1957)
[7] Ronald J. GouldUpdating the Hamiltonian Problem — A Survey. Journal of Graph Theory, vol. 15, no. 2, pp 121-157, (1991) · Zbl 0746.05039
[8] F. Thomson LeightonIntroduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes Morgan Kaufmann Publishers, Chapter 3, page 509, (1991)
[9] Burkhard Monien, Hal SudboroughComparing Interconnection Networks. MFCS 88, pp 138-153, (1988)
[10] Franco P. Preparata, J. VuilleminThe Cube-Connected-Cycles. A Versatile Network for Parallel Computation. IEEE FOCS vol. 20, pp140-147, (1979)
[11] Maheswara R. Samatham, Dhiraj K. Pradhan The DeBruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI. IEEE Transactions on Computers vol. 20, no. 4, pp 567-581, (1989) · Zbl 0671.94028
[12] Alan M. Schwartz, Michael C. LouiDictionary Machines on Cube-Class Networks. IEEE Transactions on Computers vol. C-36, no. 1, pp 100-105, (1987)
[13] Harold S. StoneParallel Processing with the Perfect Shuffle. IEEE Transactions on Computers vol. C-20, no. 2, pp 153-161, (1971) · Zbl 0214.42703
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.