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
On ad hoc routing with guaranteed delivery
Full text PdfPdf (197 KB)
Source
Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents
Toronto, Canada
SESSION: B1-1 table of contents
Pages 418-418  
Year of Publication: 2008
ISBN:978-1-59593-989-0
Author
Mark Braverman  University of Toronto, Toronto, ON, Canada
Sponsors
SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 6,   Downloads (12 Months): 67,   Citation Count: 0
Additional Information:

abstract   references   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/1400751.1400809
What is a DOI?

ABSTRACT

We give a simple poly-time log-space ad hoc routing algorithm in static networks with a logarithmic overhead on the message size. The algorithm provides guaranteed delivery using universal exploration sequences.


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
M. Braverman, On ad hoc routing with guaranteed delivery, e-print 0804.0862 on arxiv.org, 2008.
 
2
S. Durocher, D. Kirkpatrick and L. Narayanan,On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks.In Proc. of ICDCN 2008. Springer LNCS 4904:546--557, 2008.
 
3
O. Reingold, Undirected ST-Connectivity in Log-Space, ECCC report TR04-094, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems


General Terms:
Algorithms, Reliability, Theory


Keywords:
ad hoc routing, derandomization, space-bounded computation, universal exploration sequence

Collaborative Colleagues:
Mark Braverman: 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