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...
| Publicat a: | Journal of the ACM 51, 6 (2004). |
|---|---|
| Autor principal: | |
| Format: | Article |
| Idioma: | English |
| Matèries: |