| Abstract |
|
Concentrators and generalized-concentrators are interconnection networks that provide respectively pairwise vertex-disjoint directed paths and trees to satisfy interconnection requests. An interconnection network is non-blocking in the strict sense if every compatible interconnection request can be satisfied by a path regardless of any existing interconnections. We present an interconnection property equivalent to the generalized-concentration with constrained network capacity and request multiplicity in the strictly non-blocking context, and show a polynomial-time computational complexity result for deciding the strictly non-blocking generalized-concentration properties with constrained network parameters, by using b-matching techniques.
|
 Additional Information
|
Index Terms- computational complexity, interconnection networks, generalized-concentrators, concentrators, b-matchings, network flows
Citation:
H.K. Dai,
"Deciding Strictly Non-Blocking Generalized-Concentration Properties with Constrained Network Parameters,"
ispan,
p. 22,
1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99),
1999
|
