Compact routing with minimum stretch

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Compact routing with minimum stretch

Full text

Pdf (616 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland, United States

Pages: 255 - 260

Year of Publication: 1999

ISBN:0-89871-434-6

Author

Lenore J. Cowen

Department of Mathematical Sciences, Department of Computer Science, Johns Hopkins University, Baltimore, MD

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIAM : Society for Industrial and Applied Mathematics

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 47, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Aingworth, C. Chekuri, P. Indyk, and R. Motwa.ni. Fast estimation of diameter and shortest paths (without matrix multiplication). Unpublished manuscript.
	2	D. Aingworth , C. Chekuri , R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.547-553, January 28-30, 1996, Atlanta, Georgia, United States
	3	Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
	4	B. Awerbuch , A. Bar-Noy , N. Linial , D. Peleg, Compact distributed data structures for adaptive routing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.479-489, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73053]
	5	Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
	6	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999 [doi>10.1137/S0097539794271898]
	7	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	8	Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
	9	Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.93-102, January 05-07, 1997, New Orleans, Louisiana, United States
	10	D. Dor , S. Halperin , U. Zwick, All pairs almost shortest paths, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.452, October 14-16, 1996
	11	Tamar Eilam , Cyril Gavoille , David Peleg, Compact routing schemes with low stretch factor (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.11-20, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277702]
	12	G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171-190, Aug. 1988.
	13	Greg N. Frederickson , Ravi Janardan, Efficient message routing in planar networks, SIAM Journal on Computing, v.18 n.4, p.843-857, Aug. 1989 [doi>10.1137/0218058]
	14	C. Gavoille. A survey on interval routing scheme. Technical Memo RR-1182-97, Laboratoire Bordelais de Recherche en Informatique, Oct. 1997.
	15	C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor three. In #th International Colloquium on Structural Informtion and Communication Complexity (SIROCCO), pages 162-175, July 1997.
	16	L. Lovasz. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975.
	17	D. Peleg and A. A. SchS.ffer. Graph spanners. J. of Graph Theory, 13:99-116, 1989.
	18	David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62217]
	19	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
	20	N. Santoro and R. Khatib. Implicit routing in networks. The Computer Science Journal, 28:5-8, 1985.
	21	J. van Leeuwen and R. Tan. Routing with compact routing tables. In G. Roznenberg and A. Salomaa, editors, The Book of L, p#ges 259-273. Springer-Verlag, New York, New York, 1986.
	22	J. Van Leeuwen , R. B. Tan, Interval routing, The Computer Journal, v.30 n.4, p.298-307, Aug. 1987 [doi>10.1093/comjnl/30.4.298]

CITED BY 15

	Cyril Gavoille, Routing in distributed networks: overview and open problems, ACM SIGACT News, v.32 n.1, March 2001
	Kazuo Iwama , Akinori Kawachi, Compact routing with stretch factor of less than three (brief announcement), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.337, July 16-19, 2000, Portland, Oregon, United States
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing for digraphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.885-886, January 17-19, 1999, Baltimore, Maryland, United States
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.51-59, July 16-19, 2000, Portland, Oregon, United States
	Kevin C. Zatloukal , Nicholas J. A. Harvey, Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Lenore J. Cowen , Christopher G. Wagner, Compact roundtrip routing in directed networks, Journal of Algorithms, v.50 n.1, p.79-95, January 2004
	Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Kazuo Iwama , Masaki Okita, Compact routing for average-case networks, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
	Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-12, June 2008
	Byung-Gon Chun , Sylvia Ratnasamy , Eddie Kohler, NetComplex: a complexity metric for networked system designs, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.393-406, April 16-18, 2008, San Francisco, California
	Cedric Westphal , James Kempf, A compact routing architecture for mobility, Proceedings of the 3rd international workshop on Mobility in the evolving internet architecture, August 22-22, 2008, Seattle, WA, USA
	Huaiyuan Ma , Otto J. Wittner , Bjarne E. Helvik, A stochastic clustering algorithm for swarm compact routing, Proceedings of the 5th Euro-NGI conference on Next Generation Internet networks, p.78-85, July 01-03, 2009, Aveiro, Portugal