An Upper Bound Result for Multi-label Interval Routing on Planar Graphs.
Savio S. H. Tse, Francis C. M. Lau · PolyU Institutional Research Archive (Hong Kong Polytechnic University) · 2002
Interval routing is a space-efficient routing method for computer networks. In this paper, all graphs are assumed to be planar graphs, unless specified otherwise. We have four upper bound results in this paper. First, for D ≥ 3, we prove the existence of an O(D 4 )-IRS on arbitrary graphs whose longest path is bounded by D, where D is the diameter not less than three. With a little modification, we can reduce the number of labels used to O(D 3 ) with the length of longest path being increased to (1 + α)D, where α is any constant in (0, 1). Together with the result in Theorem 4 of [14], this result implies an O(n 3