On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
On a Family of Strong Geometric Spanners That Admit Local Routing Strategies
复制标题
关于允许本地路由策略的强几何扳手系列
DOI：
10.1007/978-3-540-73951-7_27
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Daming Xu
中科院分区：
文献类型：
--
作者：
P. Bose;Paz Carmi;M. Couture;M. Smid;Daming Xu
我们引入了一类依赖于两个参数λ和θ的有向几何图，记为。对于和，图是一个强图，对于。图中节点的出度最大为。其次，我们证明了所有的强空间也是单位圆盘图的空间。对不同参数λ和θ值的模拟表明，对于随机点集，的生成比优于已证明的理论界.
We introduce a family of directed geometric graphs, denoted, that depend on two parametersλandθ. Forand, thegraph is a strongt-spanner, with. The out-degree of a node in thegraph is at most. Moreover, we show that routing can be achieved locally on. Next, we show that all strongt-spanners are alsot-spanners of the unit disk graph. Simulations for various values of the parametersλandθindicate that for random point sets, the spanning ratio ofis better than the proven theoretical bounds.