A space lower bound for name-independent compact routing in trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A space lower bound for name-independent compact routing in trees

Full text

Pdf (61 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures table of contents

Las Vegas, Nevada, USA

SESSION: Brief announcements table of contents

Pages: 216 - 216

Year of Publication: 2005

ISBN:1-58113-986-1

Authors

Kofi A. Laing	Tufts University, Medford, MA
Rajmohan Rajaraman	Northeastern University, Boston, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 3

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1073970.1074005 What is a DOI?

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	I. Abraham, C. Gavoille, and D. Malkhi. Routing with improved communication-space trade-off. In Proc. 18th Int'l. Symp. on Distrib. Computing (DISC), Oct 2004.
	2	Pierre Fraigniaud , Cyril Gavoille, A Space Lower Bound for Routing in Trees, Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science, p.65-75, March 14-16, 2002
	3	C. Gavoille and M. Gengler. Space-efficiency of routing schemes of stretch factor three. In 4th (SIROCCO), pages 162--175, July 1997.
	4	Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	5	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]

CITED BY 3

	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: lower bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi, On space-stretch trade-offs: upper bounds, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Dmitri Krioukov , k c claffy , Kevin Fall , Arthur Brady, On compact routing for the internet, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007