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

John D. Carpinelli, A. Yavuz Oruc

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)319-326
Number of pages8
Issue number6
StatePublished - Sep 1994

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Applications of matching and edge‐coloring algorithms to routing in clos networks'. Together they form a unique fingerprint.

Cite this