Premium
Applications of matching and edge‐coloring algorithms to routing in clos networks
Author(s) -
Carpinelli John D.,
Oruc A. Yavuz
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240603
Subject(s) - clos network , bipartite graph , matching (statistics) , enhanced data rates for gsm evolution , edge coloring , computer science , routing (electronic design automation) , connection (principal bundle) , algorithm , routing algorithm , theoretical computer science , mathematics , computer network , graph , artificial intelligence , routing protocol , statistics , geometry , line graph , graph power
Rearrangeable Clos networks have been studied in the literature in connection with telephone switching and communication networks. This paper examines the applicability of matching and edge‐coloring in bipartite graphs to the rearrangement problem in these networks. A survey of various matching and edge‐coloring algorithms is given, and these algorithms are evaluated for their suitability and effectiveness. It is shown that no single matching or edge‐coloring algorithm reported in the literature performs well over all Clos networks. It is further shown that the time complexity of the looping algorithm for Beneš networks is at least as good as any routing algorithm that can be obtained from matching or edge‐coloring. © 1994 by John Wiley & Sons, Inc.