Simpler O(1) Query Algorithm for Level Ancestors
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916338283315200 |
|---|---|
| author | Saxena, Sanjeev |
| author_facet | Saxena, Sanjeev |
| contents | This note describes a very simple O(1) query time algorithm for finding level ancestors. This is basically a serial (re)-implementation of the parallel algorithm of Berkman and Vishkin (O.Berkman and U.Vishkin, Finding level-ancestors in trees, JCSS, 48, 214--230, 1994).
Although the basic algorithm has preprocessing time of O(n log n), by having additional levels or using table lookup, the preprocessing time can be reduced to almost linear or linear.
The table lookup algorithm can be built in O(1) parallel time with $n$ processors and can also be used to simplify the parallel algorithm of Berkman and Vishkin and make it optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_11954 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Simpler O(1) Query Algorithm for Level Ancestors Saxena, Sanjeev Data Structures and Algorithms This note describes a very simple O(1) query time algorithm for finding level ancestors. This is basically a serial (re)-implementation of the parallel algorithm of Berkman and Vishkin (O.Berkman and U.Vishkin, Finding level-ancestors in trees, JCSS, 48, 214--230, 1994). Although the basic algorithm has preprocessing time of O(n log n), by having additional levels or using table lookup, the preprocessing time can be reduced to almost linear or linear. The table lookup algorithm can be built in O(1) parallel time with $n$ processors and can also be used to simplify the parallel algorithm of Berkman and Vishkin and make it optimal. |
| title | Simpler O(1) Query Algorithm for Level Ancestors |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2207.11954 |