Compact roundtrip routing for digraphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compact roundtrip routing for digraphs

Full text

Pdf (233 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: 885 - 886

Year of Publication: 1999

ISBN:0-89871-434-6

Authors

Lenore J. Cowen	Department of Mathematical Sciences, Johns Hopkins University, Baltimore, MD
Christopher G. Wagner	Department of Mathematical Sciences, 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): 3, Downloads (12 Months): 21, Citation Count: 4

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. Motwani. 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	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]
	4	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]
	5	B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear cost constructions of neighborhood covers in sequential and distributed environments and their applications. In Proc. 34rd IEEE Syrup. on Found. o:{ Comp. Science, pages 638-647. IEEE, Nov. 1993.
	6	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]
	7	E. Cohen. Fast algorithms for constructing t-spanners and paths with stretch t. In Proc. 34rd IEEE Syrup. on Found. o} Comp. Science, pages 648-657. IEEE, Nov. 1993.
	8	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
	9	Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.255-260, January 17-19, 1999, Baltimore, Maryland, 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	T. Eilam, C. Gavoille, and D. Pdeg. Compact routing schemes with low stretch factor. Technical Memo RR-1195-98, Laboratoire Bordelais de Recherche en Informatique, Jan. 1998. To appear in PODC98.
	12	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]
	13	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]

CITED BY 4

	Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
	Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.43-52, July 13-16, 2003, Boston, Massachusetts
	Iam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008
	Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Journal of Computer and System Sciences, v.74 n.5, p.775-795, August, 2008