.png){kind=icon}
返回
Practical Compact Routing on Random Unit Disk Graphs
.png){kind=icon}
PRE
AI
DOI：10.1145/3778347.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种用于连通随机单位圆盘图的简洁实用的紧凑路由算法。基于紧凑且平衡的顶点分隔符，通过递归嵌套划分n个顶点的图，我们在预处理步骤中构造出每个顶点平均包含O(log2 n)个表项的路由表。这些路由表支持基于握手协议的路由，其中握手过程可以类似DNS查询的方式进行实现。我们的路由算法保证在图中可达，且开销适度。我们描述了该算法的一个基本版本，其需要可修改的头部；以及一个更高级的版本，该版本消除了这一需求且开销更小。
Keyword:
Routing
unit disk graph
shortest path
期刊
IF:
4.7
论文数:
1.0K
被引数:
2.0K
机构
引用论文
Geometric separation and exact solutions for the parameterized independent set problem on disk graphs几何划分和参数化独立集问题的精确解法在圆盘图中的应用
.png){kind=icon}
PREAI
分享收藏
分享收藏
查看更多内容