THE SHUFFLE-EXCHANGE NETWORK HAS A HAMILTONIAN PATH

Authors
FELDMANN R MYSLIWIETZ P
Citation
R. Feldmann et P. Mysliwietz, THE SHUFFLE-EXCHANGE NETWORK HAS A HAMILTONIAN PATH, Mathematical systems theory, 29(5), 1996, pp. 471-485
Citations number
13
Categorie Soggetti
System Science","Mathematics, Pure","Computer Science Theory & Methods",Mathematics
Journal title
Mathematical systems theory → ACNP
ISSN journal
00255661
Volume
29
Issue
5
Year of publication
1996
Pages
471 - 485
Database
ISI
SICI code
0025-5661(1996)29:5<471:TSNHAH>2.0.ZU;2-T
Abstract
We prove the existence of a Hamiltonian path in the Shuffle Exchange n etwork SX(n). This problem has been posed as an open problem by Leight on in [8] and Samatham and Pradhan in [11]. Its positive solution has several consequences showing the computational abilities of the SX(n).