Relaxed Spanners for Directed Disk Graphs

被引:3
作者
Peleg, D. [1 ]
Roditty, L. [2 ]
机构
[1] Weizmann Inst Sci, Dept Comp Sci & Appl Math, IL-76100 Rehovot, Israel
[2] Bar Ilan Univ, Dept Comp Sci, IL-52900 Ramat Gan, Israel
关键词
Directed graphs; Spanners; Disk graphs;
D O I
10.1007/s00453-011-9580-8
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Let (V,delta) be a finite metric space, where V is a set of n points and delta is a distance function defined for these points. Assume that (V,delta) has a doubling dimension d and assume that each point paV has a disk of radius r(p) around it. The disk graph that corresponds to V and r(a <...) is a directed graph I(V,E,r), whose vertices are the points of V and whose edge set includes a directed edge from p to q if delta(p,q)a parts per thousand currency signr(p). In Peleg and Roditty (Proc. 7th Int. Conf. on Ad-Hoc Networks and Wireless (AdHoc-NOW), pp. 622-633, 2008) we presented an algorithm for constructing a (1+I mu)-spanner of size O(nI mu (-d) logM), where M is the maximal radius r(p). The current paper presents two results. The first shows that the spanner of Peleg and Roditty (in Proc. 7th Int. Conf. on Ad-Hoc Networks and Wireless (AdHoc-NOW), pp. 622-633, 2008) is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of M. The second result shows that by slightly relaxing the requirements and allowing a small augmentation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph I(V,E,r (1+I mu) ), where r (1+I mu) (p)=(1+I mu)a <...r(p) for every paV, then it is possible to get a (1+I mu)-spanner of size O(n/I mu (d) ) for I(V,E,r). Our algorithm is simple and can be implemented efficiently.
引用
收藏
页码:146 / 158
页数:13
相关论文
共 13 条
[1]   A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs [J].
Baswana, Surender ;
Sen, Sandeep .
RANDOM STRUCTURES & ALGORITHMS, 2007, 30 (04) :532-563
[2]   Sparse distance preservers and additive spanners [J].
Bollobás, B ;
Coppersmith, D ;
Elkin, M .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 19 (04) :1029-1055
[3]  
Cowen Lenore J., 1999, PROC 10 ANN ACM SIAM, P885, DOI DOI 10.5555/314500.315068
[4]   All-pairs almost shortest paths [J].
Dor, D ;
Halperin, S ;
Zwick, U .
SIAM JOURNAL ON COMPUTING, 2000, 29 (05) :1740-1759
[5]   Geometric spanners for routing in mobile networks [J].
Gao, J ;
Guibas, LJ ;
Hershberger, J ;
Zhang, L ;
Zhu, A .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2005, 23 (01) :174-185
[6]   Deformable spanners and applications [J].
Gao, Jie ;
Guibas, Leonidas J. ;
Nguyen, An .
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2006, 35 (1-2) :2-19
[7]   Fast construction of nets in low-dimensional metrics and their applications [J].
Har-Peled, S ;
Mendel, M .
SIAM JOURNAL ON COMPUTING, 2006, 35 (05) :1148-1184
[8]   Localized Delaunay triangulation with application in Ad Hoc wireless networks [J].
Li, XY ;
Calinescu, G ;
Wan, PJ ;
Wang, Y .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2003, 14 (10) :1035-1047
[9]  
Peleg D., 2008, P 7 INT C AD HOC NET, P622
[10]  
Roditty L., 2007, ACM S COMPUTATIONAL, P373