TR-95-17: Complexity of Boolean Routing
杏吧原创 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.