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

John D. Carpinelli, A. Yavuz Oruc

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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
JournalNetworks
Volume24
Issue number6
DOIs
StatePublished - Sep 1994

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

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