DocumentCode
3558489
Title
An optimal O(NlgN) algorithm for permutation admissibility to extra-stage cube-type networks
Author
Shen, Xiaojun
Author_Institution
Comput. Sci. Telecommun. Program, Missouri Univ., Kansas City, MO, USA
Volume
44
Issue
9
fYear
1995
fDate
9/1/1995 12:00:00 AM
Firstpage
1144
Lastpage
1149
Abstract
A k-EMCTN is obtained by adding k more stages in front of a multistage cube-type network (MCTN). It is shown that a permutation is admissible to a k-EMCTN if and only if the conflict graph is 2k -colorable. For the case k=1, an O(NlgN) algorithm is given for constructing the conflict graph, which leads to an O(NlgN) admissibility algorithm. Furthermore, it is shown that Ω(NlgN) bits must be checked in the binary representation of a permutation for determining its admissibility
Keywords
computational complexity; graph colouring; graph theory; multistage interconnection networks; parallel algorithms; O(NlgN) admissibility algorithm; binary representation; conflict graph; extra-stage cube-type networks; graph colouring; multistage cube-type network; optimal O(NlgN) algorithm; permutation admissibility; Cities and towns; Delay; Fault tolerant systems; Network servers; Processor scheduling; Protocols; Real time systems; Scheduling algorithm; Transform coding; Video compression;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
Conference_Location
9/1/1995 12:00:00 AM
ISSN
0018-9340
Type
jour
DOI
10.1109/12.464393
Filename
464393
Link To Document