Optimal bounds on a tree inference algorithm
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913596972204032 |
|---|---|
| author | Gardiner, Jack Andrew, Lachlan L. H. Gan, Junhao Honorio, Jean Umboh, Seeun William |
| author_facet | Gardiner, Jack Andrew, Lachlan L. H. Gan, Junhao Honorio, Jean Umboh, Seeun William |
| contents | This paper tightens the best known analysis of Hein's 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the number of length queries required for a degree-$k$ tree of $n$ leaves is $O(n k \log_k n)$, which is the lower bound. It also presents a family of trees for which the performance is asymptotically better, and shows that no such family exists for a competing $O(n k \log_k n)$ algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_03138 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal bounds on a tree inference algorithm Gardiner, Jack Andrew, Lachlan L. H. Gan, Junhao Honorio, Jean Umboh, Seeun William Data Structures and Algorithms This paper tightens the best known analysis of Hein's 1989 algorithm to infer the topology of a weighted tree based on the lengths of paths between its leaves. It shows that the number of length queries required for a degree-$k$ tree of $n$ leaves is $O(n k \log_k n)$, which is the lower bound. It also presents a family of trees for which the performance is asymptotically better, and shows that no such family exists for a competing $O(n k \log_k n)$ algorithm. |
| title | Optimal bounds on a tree inference algorithm |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.03138 |