Document Type
Article
Department
Mathematics (HMC)
Publication Date
1985
Abstract
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 ( n^{1 + 1 / k} ( \log n )^{( k - 1 )/ 2} )$ edges. This is asymptotically the best explicit construction known for generalized connectors.
Rights Information
© 1985 Society for Industrial and Applied Mathematics
Recommended Citation
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.
COinS