Tail Bounds for the Wiener Index of Random Trees
Upper and lower bounds for the tail probabilities of the Wiener index of random binary search trees are given. For upper bounds the moment generating function of the vector of Wiener index and internal path length is estimated. For the lower bounds a tree class with sufficiently large probability an...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3524/pdf |
| _version_ | 1797270448932651008 |
|---|---|
| author | Tämur Ali Khan Ralph Neininger |
| author_facet | Tämur Ali Khan Ralph Neininger |
| author_sort | Tämur Ali Khan |
| collection | DOAJ |
| description | Upper and lower bounds for the tail probabilities of the Wiener index of random binary search trees are given. For upper bounds the moment generating function of the vector of Wiener index and internal path length is estimated. For the lower bounds a tree class with sufficiently large probability and atypically large Wiener index is constructed. The methods are also applicable to related random search trees. |
| first_indexed | 2024-04-25T02:04:26Z |
| format | Article |
| id | doaj.art-cf6277a1eb7a44939fdf4ee6ce260d65 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:04:26Z |
| publishDate | 2007-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-cf6277a1eb7a44939fdf4ee6ce260d652024-03-07T14:34:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502007-01-01DMTCS Proceedings vol. AH,...Proceedings10.46298/dmtcs.35243524Tail Bounds for the Wiener Index of Random TreesTämur Ali Khan0Ralph Neininger1Department for Mathematics and Computer ScienceDepartment for Mathematics and Computer ScienceUpper and lower bounds for the tail probabilities of the Wiener index of random binary search trees are given. For upper bounds the moment generating function of the vector of Wiener index and internal path length is estimated. For the lower bounds a tree class with sufficiently large probability and atypically large Wiener index is constructed. The methods are also applicable to related random search trees.https://dmtcs.episciences.org/3524/pdfrandom treeswiener index[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Tämur Ali Khan Ralph Neininger Tail Bounds for the Wiener Index of Random Trees Discrete Mathematics & Theoretical Computer Science random trees wiener index [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Tail Bounds for the Wiener Index of Random Trees |
| title_full | Tail Bounds for the Wiener Index of Random Trees |
| title_fullStr | Tail Bounds for the Wiener Index of Random Trees |
| title_full_unstemmed | Tail Bounds for the Wiener Index of Random Trees |
| title_short | Tail Bounds for the Wiener Index of Random Trees |
| title_sort | tail bounds for the wiener index of random trees |
| topic | random trees wiener index [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3524/pdf |
| work_keys_str_mv | AT tamuralikhan tailboundsforthewienerindexofrandomtrees AT ralphneininger tailboundsforthewienerindexofrandomtrees |