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.gif>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.gif>HTML (Source code)  <html.gif>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},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 22.05.2015.