The Compactness of Interval Routing

摘要: The compactness of a graph measures the space complexity its shortest path routing tables. Each outgoing edge node x is assigned (pairwise disjoint) set addresses, such that unique containing address y first from to y. measure used in context interval minimum number intervals consecutive addresses needed represent each set, minimized over all possible choices and paths. This paper establishes asymptotically tight bounds n/4 on an n-node graph. More specifically, it shown every has at most n/4+o(n), conversely, there exists whose - o(n). Both improve upon known results. (A preliminary version lower bound been partially published Proceedings 22nd International Symposium Mathematical Foundations Computer Science, Lecture Notes Comput. Sci. 1300, pp. 259--268, 1997.)