The complexity of deciding strictly non-blocking concentration and generalized-concentration properties with small depth
H. K. Dai · 2002
The practicality of the probabilistic construction of interconnection networks depends on the difficulty of deciding if a random structure satisfies the desired interconnection property, or of identifying a defective one. Polynomial-time computational complexity results are presented for deciding the strictly non-blocking concentration and generalized concentration properties with small depth, by using b-matching techniques.>