Carleton University
Technical Report TR-95-17
July 1995
Complexity of Boolean Routing
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
Abstract
We use the technique of Kolmogorov complexity to obtain lower bounds for boolean routing. For any integers n, d, we construct networks G on n vertices and degree O(d), which require Ω(nd log d/ log n) memory bits per router on n log d= logn routers and hence a total ofΩ(n2d log2 d/ log2 n)
memory bits for any full information routing scheme on the graph. The lower bound is tight when log d / log n is constant.