Name
Abstract | ||
|---|---|---|
This paper presents some analytic results concerning the pivot interval routing (PIR) strategy of [T. Eilam, C. Gavoille, D. Peleg, Compact routing schemes with low stretch factor, J. Algorithms 46(2) (2003) 97-114, Preliminary version appeared. in: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, June 1998, pp. 11-20.] That strategy allows message routing on every weighted n-node network along paths whose stretch (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at most three, with routing tables of size O(nlog^3^/^2n) bits per node. In addition, the route lengths are at most 2D (@?1.5D@? for uniform weights) where D is the weighted diameter of the network. The PIR strategy can be constructed in polynomial time and can be implemented so that the generated scheme is in the form of an interval routing scheme (IRS), using at most O(nlogn) intervals per link. Here, it is shown that there exists an unweighted n-node graph G and an identity assignment ID for its nodes such that for every R@?PIR on G with a set of pivots computed by a greedy cover algorithm (respectively, a randomized algorithm), AvStr"G(R)3-o(1) (respectively, with high probability). Also, it is shown that for almost every unweighted n-node graph G, and for every R@?PIR on G, AvStr"G(R)=1.875+/-o(1). A comparison between PIR and HCP"k, the hierarchical routing strategy presented in [B. Awerbuch, A. Bar-Noy, N. Linial, D. Peleg, Improved routing strategies with succinct tables, J. Algorithms 11 (1990) 307-341.] is also given. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2006.09.010 | Discrete Applied Mathematics |
Keywords | Field | DocType |
average stretch,stretch factor,compact routing scheme,compact routing schemes,message routing,j. algorithms,hierarchical routing strategy,average stretch analysis,interval routing schemes,pivot interval routing,interval routing scheme,unweighted n-node graph,pir strategy,improved routing strategy,distributed computing,hierarchical routing,polynomial time,randomized algorithm | Stretch factor,Randomized algorithm,Graph,Discrete mathematics,Combinatorics,Message routing,Hierarchical routing,Greedy algorithm,Routing table,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
155 | 5 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.36 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tamar Eilam | 1 | 445 | 29.81 |
| Cyril Gavoille | 2 | 1526 | 114.20 |
| David Peleg | 3 | 6662 | 824.19 |