.png){kind=icon}
.png){kind=icon}
Return
Practical Compact Routing on Random Unit Disk Graphs
.png){kind=icon}
PRE
AI
DOI：10.1145/3778347.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We describe a simple and practical algorithm for compact routing on connected random unit disk graphs. Using a recursive nested dissection of an n-vertex graph based on compact and balanced vertex separators, we construct routing tables with an average of O(log2 n) entries per vertex in a preprocessing step. The routing tables then support handshaking-based routing, where the handshaking can be implemented similarly to a DNS lookup. Our routing algorithm is guaranteed to deliver on the graph, while incurring moderate stretch. We describe a basic version of the algorithm that requires modifiable headers and a more advanced version that eliminates this need and incurs less stretch.
Keywords:
Routing
unit disk graph
shortest path
Journal
IF:
4.7
Papers:
994
Citations:
2.0K