Applications of matching and edge‐coloring algorithms to routing in clos networks

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.