Multicommodity Flows in Simple Multistage Networks
Ehab S. Elmallah and Joseph Culberson
Date: July 1994
University of Alberta Computing Science Technical Report TR94-11
Abstract
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 3-stage networks. Using 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 2 secondary switches.
In contrast, the problem is shown to be NP-complete if the network has 3 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 arbitrary size.
The notion of extra-stage 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
extra-stage hypercubic networks. In contrast, we show that the multicommodity
flow problem is NP-complete on extra-stage networks, even if r=6, each link has
an integral capacity <= 3, and all flow demands are equal.
TR 94-11 can also be retrieved by
anonymous ftp ftp.cs.ualberta.ca pub/TechReports
Queries: email ehab@cs.ualberta.ca
or joe@cs.uvic.ca
Joseph Culberson
May 17,1994