The design of optimum connection blocks of field programmable gate arrays (FPGA's) in number and in distribution of switches is formulated as a bipartite graph design problem and solved. A bipartite with vertex sets R and L (|R|/spl les/|L|) is called totally perfect if there is a perfect matching from L/sub s/ to R for any L/sub s//spl sub/L with |L/sub s/|/spl les/|R|. The difference of maximum and minimum degrees of the vertices in L or R is called the skew of the respective vertex set. The problem is to construct a minimum totally perfect bipartite graph with the minimum skew. The result shows that a method, biscattering, can construct such a matrix in O(|R|/spl times/|L|) time where the lower bound is attained for both skews. This construction also solves the problem of designing optimum direct-concentrators.

The optimal design problem of the connection-blocks of FPGA with respect to the number of switches and their distribution is solved. This also concerns with the optimal construction of direct concentrators.>