Back to Search
Start Over
Reachability Problems for Transmission Graphs.
- Source :
-
Algorithmica . Oct2022, Vol. 84 Issue 10, p2820-2841. 22p. - Publication Year :
- 2022
-
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 | p q | ≤ r p for any two points p and q in P, where |pq| 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 84
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 159441262
- Full Text :
- https://doi.org/10.1007/s00453-022-00985-1