Title :
The complexity of deciding strictly non-blocking concentration and generalized-concentration properties with small depth
Author_Institution :
Dept. of Comput. Sci., North Dakota Univ., Grand Forks, ND, USA
Abstract :
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
Keywords :
computational complexity; decidability; b-matching techniques; decidability; defective structure identification; generalized concentration properties; interconnection networks; polynomial-time computational complexity; probabilistic construction; random structure; small depth; strictly nonblocking concentration properties; Computational complexity; Computer networks; Computer science; Concurrent computing; Information resources; Integrated circuit interconnections; Mediation; Multiprocessor interconnection networks; Pattern analysis; Polynomials;
Conference_Titel :
Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on
Conference_Location :
Sudbury, Ont.
Print_ISBN :
0-8186-4212-2
DOI :
10.1109/ICCI.1993.315405
