On finding minimum spanning trees (Introduction in Finnish)
Author:Jyrki Katajainen
Publication:Licentiate Thesis, Department of Computer Science, University of Turku (1983), vi+115 pp.
Full text:<pdf.gif>PDF (7.82 MB)  
Abstract:Työ koostuu kahdesta osasta — johdannosta ja kuudesta erillisestä artikkelista. Johdanto on katsaus minimaalisen virittävän puun määrääviin algoritmeihin. Viime aikoina ovat tutkimuksen kohteena olleet pahimmalta ja keskimääräiseltä suoritusajaltaan nopeat algoritmit sekä likimääräiset algoritmit, todennäköisyys- ja rinnakkaisalgoritmit.

Erillissä artikkeleissa tutustutaan tarkemmin minimaalisen virittävän puun määräämiseen moniuloitteisessa avaruudessa ja keskimäärin nopeisiin minimaalisen virittävän puun määräviin algoritmeihin. Olen tehnyt artikkelit yhteistyössä Olli Nevalaisen ja Jarmo Ernvallin kanssa. Artikkeleista kaksi on julkaistu ja kaksi julkaistaan lähitulevaisuudessa:

(1)
ERNVALL J., KATAJAINEN J., NEVALAINEN O.: A minimal spanning tree algorithm for a point set in Euclidean space, Rep. A28, Comput. Sci., Univ. of Turku (1980). (lyhennettynä aikakauslehdessä BIT 21,1 (1981), 46–54)
(2)
KATAJAINEN J.: An implementation of an algorithm for finding minmal spanning tree in a Euclidean coordinate space, Rep. D22, Comput. Sci., Univ. of Turku (1981).
(3)
KATAJAINEN J.: On the worst case of a minimal spanning tree algorithm for Euclidean space. (julkaistaan aikakauslehdessä BIT)
(4)
NEVALAINEN O., KATAJAINEN J.: Experiments with a closest point algorithm in Hamming space, Angewandte Informatik 5 (1982), 277-281.
(5)
KATAJAINEN J., NEVALAINEN O.: An alternative implementation of Kruskal’s minimal spanning tree algorithm. (julkaistaan aikakauslehdessä Science of Computer Programming)
(6)
KATAJAINEN J.: An implementation of Cheriton-Tarjan’s minimal spanning tree algorithm using ordered subsets. (käsikirjoitus)


Kolmessa ensimmäisessä artikkelissa tutkitaan minimaalisen virittävän puun määräämisen kompleksisuutta euklidisessa avaruudessa. Artikkelissa (1) on teoreettisesti analysoitu erästä algoritmia ja tutkittu sen tehokkuutta kokeellisesti. Algoritmin implementoinnin yksityiskohdat esitetään artikkelissa (2). Artikkelissa (3) esitetään eräitä erikoistapauksia, joissa algoritmi käyttäytyy pahimmalla mahdollisella tavalla. Algoritmi havaittiin kokeissa nopeaksi, kun avaruuden ulotteisuus on pieni ja pisteet ovat normaalisti jakautuneita. Nopeus perustuu suurelta osin siihen, että algoritmissa usein toistuva annetun pisteen lähimmän pisteen haku suoritetaan niin kutsutun k-d puun avulla.

Edellinen algoritmi toimii myös Hamming-metriikassa. Artikkelissa (4) tutkitaan kokeellisesti, onko k-d puu paras mahdollinen lähimmän pisteen hakua tukeva hakurakenne Hamming-metriikan tapauksessa. Burhardin ja Kellerin esittämä puurakenne, joka on suunniteltu erityisesti Hamming-metriikkaa ajatellen, osoittautuikin joskus k-d puuta paremmaksi.

Kahdessa muussa artikkelissa tutustutaan keskimääräiseltä suoritusajaltaan nopeisiin algoritmeihin. Artikkelissa (5) esitetään Kruskalin algoritmille implementointi ja osoitetaan se keskimäräisessä tapauksessa sekä teoreettisesti että kokeellisesti hyväksi. Pahimman tapauksen kompleksisuudessa on kuitenkin parantamisen varaa. Artikkelissa (6) esitetään algoritmi, jonka pahimman tapauksen kompleksisuus on Kruskalin algoritmia parempi ja joka on myös keskimääräisessä tapauksessa tehokas. Käytännön kokeissa tämä algoritmi oli kuitenkin huomattavasti Kruskalin algoritmia hitaampi.
Related:<html.gif>HTML (Technical report)  <html.gif>HTML (Source code)  <html.gif>HTML (Journal article)  <html.gif>HTML (Journal article)  <html.gif>HTML (Technical report)  
BibLATEX:
@thesis{Licentiate1983T,
  author = {Jyrki Katajainen},
  title = {On finding minimum spanning trees ({I}ntroduction in {F}innish)},
  type = {Licentiate Thesis},
  institution = {Department of Computer Science, University of Turku},
  year = {1983},
  pagetotal = {vi+115},
}
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 13.08.2012.