With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n1 + 1 / k (log n )( k - 1)/ 2 ) edges. This is asymptotically the best explicit construction known for generalized connectors.
© 1985 Society for Industrial and Applied Mathematics
Kirkpatrick, David G., Maria Klawe, and Nicholas Pippenger. “Some Graph-Colouring Theorems with Applications to Generalized Connection Networks.” SIAM Journal on Algebraic and Discrete Methods 6, no. 4 (October 1985): 576-582.