Reachability Problems for Transmission Graphs
SCIE
SCOPUS
- Title
- Reachability Problems for Transmission Graphs
- Authors
- OH, EUNJIN; 안신우
- Date Issued
- 2022-10
- Publisher
- Springer Verlag
- Abstract
- Let P be a set of n points in the plane where each point p of P is associated with a radius r(p) > 0. The transmission graph G = (P, E) of P is defined as the directed graph such that E contains an edge from p to q if and only if vertical bar pq vertical bar <= r(p) for any two points p and q in P, where vertical bar pq vertical bar denotes the Euclidean distance between p and q. In this paper, we present a data structure of size O(n(5/3)) such that for any two points in P, we can check in O(n(2/3)) time if there is a path in G between the two points. This is the first data structure for answering reachability queries whose performance depends only on n but not on the ratio between the largest and smallest radii.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/114297
- DOI
- 10.1007/s00453-022-00985-1
- ISSN
- 0178-4617
- Article Type
- Article
- Citation
- Algorithmica, vol. 84, no. 10, page. 2820 - 2841, 2022-10
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.