ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Optimal routing tables
Full text PdfPdf (1.05 MB)
Source Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing table of contents
Philadelphia, Pennsylvania, United States
Pages: 134 - 142  
Year of Publication: 1996
ISBN:0-89791-800-2
Authors
Harry Buhrman  CWI
Jaap-Henk Hoepman  CWI
Paul Vitányi  CWI and University of Amsterdam
Sponsors
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGOPS: ACM Special Interest Group on Operating Systems
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 8,   Citation Count: 2
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/248052.248076
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
Michele Flammini , Jan van Leeuwen , Alberto Marchetti-Spaccamela, The Complexity of Interval Routing on Random Graphs, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.37-49, August 28-September 01, 1995
2
Pierre Fraigniaud , Cyril Gavoille, Memory requirement for universal routing schemes, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.223-230, August 20-23, 1995, Ottowa, Ontario, Canada  [doi>10.1145/224964.224989]
3
Cyril Gavoille , Stéphane Pérennès, Memory requirement for routing in distributed networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.125-133, May 23-26, 1996, Philadelphia, Pennsylvania, United States  [doi>10.1145/248052.248075]
 
4
A.N. Kolmogorov. Three approaches to the quantitative definition of information. Problems Inform. Transmission, 1(1):1-7, 1965.
 
5
E. Kranakis and D. Krizanc. Lower bounds for compact routing schemes. Manuscript, 1995.
 
6
Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. Compact routing and shortest path information. In Proc. ~nd International Colloquium on Structu~'al lnfor~ marion and Communication Complexity. Caxleton University Press, 1995.
 
7
Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. Lower bounds for compact shortest path routing schemes. Manuscript, 1995.
 
8
Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
9
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]
 
10
H. S. Will. Algorithms a~d Cornplexit~t. Prentice-H~dl, 1986.

CITED BY  2
Cyril Gavoille , Stéphane Pérennès, Memory requirement for routing in distributed networks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.125-133, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems


General Terms:
Algorithms, Performance, Verification

Collaborative Colleagues:
Harry Buhrman: colleagues
Jaap-Henk Hoepman: colleagues
Paul Vitányi: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player