Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414276 | Computational Geometry | 2015 | 8 Pages |
Abstract
Let G be a unit disk graph in the plane defined by n disks whose positions are known. For the case when G is unweighted, we give a simple algorithm to compute a shortest path tree from a given source in O(nlogn)O(nlogn) time. For the case when G is weighted, we show that a shortest path tree from a given source can be computed in O(n1+ε)O(n1+ε) time, improving the previous best time bound of O(n4/3+ε)O(n4/3+ε).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sergio Cabello, Miha Jejčič,