Compact oracles for reachability and approximate distances in planar diagraphs.
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 O(log n) space label for each vertex and then we can determine if one vertex can reach another co...
| Published in: | Journal of the ACM 51, 6 (2004). |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | English |
| Subjects: |