Tamar Eilam
- 1.AWERBUCH, B., BAR-NOY, A., LINIAL, N., AND PE- LEG, D. Compact distributed data structures for adaptive routing. Ill 21~t Symposium on Theory of Computing (STOC) (1989), vol. 2, pp. 230-240. Google Scholar
Digital Library
- 2.AWERBUOH, B., BAR-NOY, A., LINIAL, N., AND PE- LEG, D. hnproved routing strategies with succint tables. Journal of Algorithms 11 (Feb. 1990), 307-341. Google ScholarDigital Library
- 3.AWERBUCH, B., AND PELEG, D. Sparse partitions. Ill 31th Symposium on Foundations of Computer Science (FOCS) (1990), pp. 503-513.Google ScholarDigital Library
- 4.EILAM, T., GAVOILLE, C., AND PELEG, D. Compact routing schemes with low stretch factor. Research Report RR-1195-98, LaBRI, University of Bordeaux, 351, cours de la Lib6ration, 33405 Talence Cedex, Fraslce, Jan. 1998.Google Scholar
- 5.EILAM, T., MORAN, $., AND ZAKS, $. A lower bound for linear interval routing. In 10ta International Workshop on Distributed Algorithms (WDAG) (1996), vol. 1151 of Lecture Notes in Computer Science, Springer-Verlag. Google ScholarDigital Library
- 6.FLAMMINI, M., GAMBOSI, G., NANNI, U., AND TAN, R. B. Multi-dimensional interval routing schemes. In 90 International Workshop on Distributed Algorithms (WDAG) (1995), vol. 972 of Lecture Notes ill Computer Science, Springer-Verlag. To appear in TCSA. Google ScholarDigital Library
- 7.FLAMMIN~, M., AND NARDELLI, E. On the path length in interval routing schemes. Mmmscript, 1996.Google Scholar
- 8.FRAIGN1AUD, P., AND GAVOmLE, C. Memory requiremeat for universal routing schemes. In 14~h Annual ACM Symposium on Principles of Distributed Computing (PODC) (Aug. 1995), pp. 223-230. Google ScholarDigital Library
- 9.FREDEmCKSON, G. N., AND JANARDAN, R. Seperator-based strategies for efficient message routing. in 27th Symposium on Foundations of Computer Science (FOCS) (May 1986), pp. 428-437.Google Scholar
- 10.FREDERICKSON, G. N., AND JANARDAN, R. Designing networks with compact routing tables. Algorithmica 3 (Aug. 1988), 171-190.Google ScholarDigital Library
- 11.FREDERICKSON, G. N., AND JANARDAN, R. Efficient message routing in plmmr networks. SIAM Journal on Computing 18, 4 (Aug. 1989), 843-857. Google ScholarDigital Library
- 12.FREDERiCKSON, G. N., AND JANARDAN, R. Spaceefficient message routing in c-decomposable networks. SIAM Journal on Computing 19, 1 (Feb. 1990), 164- 181. Google ScholarDigital Library
- 13.GAMBOSl, G., AND VOCCA, P. Topological routing schemes. In 10th International Workshop on Distributed Algorithms (WDAG) (Oct. 1996), vol. 1151 of Lecture Notes in Computer Science, Springer-Verlag. Google ScholarDigital Library
- 14.GAVOILLE, C. On the dilation of interval routing. In 22~a International Symposium on Mathematical Foundations of Computer Science (MFC$) (Aug. 1997), vol. 1300 of Lecture Notes in Computer Science, Springer-Verlag, pp. 259-268. Google ScholarDigital Library
- 15.GAVOILLS, C. A survey on interval routing scheme. Research Report RR-1182-97, LaBRI, University of Bordeaux, 351, cours de la Libg~ration, 33405 Talence Cedex, Fremce, Oct. 1997. Submitted for publication.Google Scholar
- 16.GAVOiLLE, C., AND GENGLER, M. Space-efficiency of routing schexnes of stretch factor three. In 4th International Colloquium on Structural Information ~4 Communication Complexity (SIROCCO) (July 1997).Google Scholar
- 17.GAVOJLLE, C., AND GU~VarMONT, E. Worst case bounds for shortest path interval routing. Research Report 95-02, LIP, t~cole Normale Sup~rieure de Lyon, 69364 Lyon Cedex 07, Frmlce, Jem. 1995. To appear in Journal of Algorithms. Google ScholarDigital Library
- 18.GAVOJLLE, C., AND PELEG, D. The compactness of interval routing. Research Report RR-1176-97, LaBRI, University of Bordeaux, 351, cours de la Lib6ration, 33405 TaIence Cedex, Fraalce, Sept. 1997. Submitted for publication.Google Scholar
- 19.GAVOILLE, C., AND PgRENNgS, S. Memory requirement for routing in distributed networks, in 15*a Annual A CM Symposium on Principles of Distributed Computing (PODC) (May 1996), pp. 125-133. Google ScholarDigital Library
- 20.HALL, M. J. Combinatorial Theory (second edition). Wiley-Interscience Publication, 1986.Google Scholar
- 21.INMOS. The TgO00 Transputer Products Overview Manual, 1991.Google Scholar
- 22.KRXX;OVIC, R., RUii(~KA, P., AND STEFANKOVIC, D. The complexity of shortest path m~d dilation bounded interval routing. In 3~a international Euro-Par Conference (Aug. 1997), vol. 1300 of Lectures Notes in Computer Science, Springer-Verlag, pp. 258-265. Google ScholarDigital Library
- 23.LovAsz, L. On the ratio of optimal integral mid fractional covers. Discrete Mathematics 13 (1975), 383- 390.Google ScholarDigital Library
- 24.PELEG, D. An overview of locality-sensitive distributed computing, Unpublished Monograph, The Weizmann Institute, Rehovot, israel, 1997.Google Scholar
- 25.PELEG, D., AND UPFAL, E. A trade-offbetween space mid efficiency for routing tables. Journal of the A CM 36, 3 (July 1989), 510-530. Google ScholarDigital Library
- 26.SANTORO, N., AND KHATIB, R. Labelling and implicit routing in networks. The Computer Journal 28, (1985 ), 5-s.Google ScholarCross Ref
- 27.TSE, S. S. H., AND LAU, F. C. M. An optimal lower bound for interval routing in general networks. In 4*a International Colloquium on Structural Information ~4 Communication Complexity (SIROCCO) (July 1997).Google Scholar
- 28.VAN LEEUWEN, J., AND TAN, R. B. Routing with compact routing table. In The Book of L (1986), Springer- Verlag, pp. 259-273.Google ScholarCross Ref
Index Terms
- Compact routing schemes with low stretch factor (extended abstract)
Recommendations
Compact routing schemes with improved stretch
PODC '13: Proceedings of the 2013 ACM symposium on Principles of distributed computingWe consider the problem of compact routing in weighted general undirected graphs, in which the goal is to construct local routing tables that allow information to be sent on short paths in the network. In this paper the first improvement to the work of ...
Compact name-independent routing with minimum stretch
Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using aÕ(√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is ...
Compact routing schemes
SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architecturesWe describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, ...
Comments