Thumbnail
Access Restriction
Subscribed

Author Thorup, Mikkel
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Planar graphs ♦ Reachability and shortest paths oracles
Abstract It is shown that a planar digraph can be preprocessed in near-linear time, producing a near-linear space oracle that can answer reachability queries in constant time. The oracle can be distributed as an $\textit{O}(log$ $\textit{n})$ space label for each vertex and then we can determine if one vertex can reach another considering their two labels only.The approach generalizes to give a near-linear space approximate distances oracle for a weighted planar digraph. With weights drawn from {0, …, $\textit{N}},$ it approximates distances within a factor (1 + ϵ) in $\textit{O}(log$ log $(\textit{nN})$ + 1/ϵ) time. Our scheme can be extended to find and route along correspondingly short dipaths.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 51
Issue Number 6
Page Count 32
Starting Page 993
Ending Page 1024


Open content in new tab

   Open content in new tab
Source: ACM Digital Library