| An alternative for the implementation of Kruskal’s minimal spanning tree algorithm | |
| Authors: | Jyrki Katajainen and Olli Nevalainen |
| Published in: | Science of Computer Programming 3,2 (1983), 205-216 |
| Full text: |  PDF (1.34 MB) |
| DOI: | 10.1016/0167-6423(83)90011-4 |
| Copyright: | © Elsevier Science Publishers B.V. |
| Abstract: | An application of the bucket sort in Kruskal’s minimal spanning tree algorithm is proposed. The modified algorithm is very fast if the edge costs are from a distribution which is close to uniform. This is due to the fact that the sorting phase then takes for an m edge graph an O(m) average time. The O(m log m) worst case occurs when there is a strong peak in the distribution of the edge costs. |
| Related: |  HTML (Source code) HTML (Thesis) |
| BibLATEX: | @article{KN1983J,
author = {Jyrki Katajainen and Olli Nevalainen},
title = {An alternative for the implementation of {K}ruskal's minimal
spanning tree algorithm},
journaltitle = {Science of Computer Programming},
volume = {3},
number = {2},
year = {1983},
pages = {205--216},
}
|