Premium
Multicommodity flows in simple multistage networks
Author(s) -
Elmallah E. S.,
Culberson J. C.
Publication year - 1995
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.3230250104
Subject(s) - bipartite graph , simple (philosophy) , mathematics , class (philosophy) , interconnection , discrete mathematics , flow (mathematics) , flow network , combinatorics , multi commodity flow problem , maximum flow problem , multistage interconnection networks , binary number , time complexity , computer science , topology (electrical circuits) , mathematical optimization , graph , arithmetic , computer network , philosophy , geometry , epistemology , artificial intelligence
In this paper, we consider the integral multicommodity flow problem on directed graphs underlying two classes of multistage interconnection networks. In one direction, we consider three‐stage networks. Using existing results on ( g , f )‐factors of bipartite graphs, we show sufficient and necessary conditions for the existence of a solution when the network has at most two secondary switches. In contrast, the problem is shown to be NP‐complete if the network has three or more secondaries. In a second direction, we introduce a recursive class of networks that includes multistage hypercubic networks (such as the omega network, the indirect binary n ‐cube, and the generalized cube network) as a proper subset. Networks in the new class may have an arbitrary number of stages. Moreover, each stage may contain identical switches of any arbitrary size. The notion of extrastage networks is extended to the new class, and the problem is shown to have polynomial time solutions on r ‐stage networks where r = 3 or where each link has a unit capacity and r ≥ 3. The latter result implies an efficient algorithm for deciding admissible permutations on conventional extrastage hypercubic networks. In contrast, we show that the multicommodity flow problem is NP‐complete on extrastage networks, even if r = 6, each link has an integral capacity ≤ 3, and all flow demands are equal.