Routing algorithms for the shuffle-exchange permutation network

For a natural number n , let S n denote the symmetric group on n letters. Let SEP n be the Cayley graph Cay ( S n , { σ , σ - 1 , τ } ) , where τ = ( 12 ) and σ = ( 1 , … , n ) . In this note, we present an easy static routing algorithm for SEP n which gives us an exact formula for the path between...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of supercomputing 2021, Vol.77 (10), p.11556-11574
Main Authors: Khosravi, Behnam, Khosravi, Behrooz, Khosravi, Bahman
Format: Article
Language:English
Subjects:
Algorithms
Compilers
Computer Science
Interpreters
Mathematical analysis
Permutations
Processor Architectures
Programming Languages
Routing (telecommunications)
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a natural number n , let S n denote the symmetric group on n letters. Let SEP n be the Cayley graph Cay ( S n , { σ , σ - 1 , τ } ) , where τ = ( 12 ) and σ = ( 1 , … , n ) . In this note, we present an easy static routing algorithm for SEP n which gives us an exact formula for the path between every pair of nodes in SEP n and it does not need any calculations. Also, we show that an upper bound of this algorithm is ⌊ ( 3 n + 1 ) 2 / 9 ⌋ . Furthermore, we use our results to present a dynamic routing algorithm for SEP n which needs at most n calculations for routing and also it does not need large amount of memory for routing tables.
ISSN:0920-8542
1573-0484
DOI:10.1007/s11227-021-03694-8