algoritmo di Borůvka

L'algoritmo di Borůvka è un algoritmo per la ricerca di un albero ricoprente minimo in un grafo in cui il peso di ciascuna coppia di archi sia distinto. Se due archi hanno peso uguale, è sufficiente modificare anche minimamente il peso di uno dei due archi per rendere valido l'algoritmo. L'algoritmo venne pubblicato nel 1926 da come metodo di costruzione di un'efficiente rete elettrica per la Moravia (Repubblica Ceca).L'algoritmo fu riscoperto da Choquet nel 1938; successivamente da , Łukasiewicz, , Steinhaus, e Zubrzycki nel 1951; e ancora da probabilmente all'inizio degli anni '60. Dato che Sollin fu l'unico informatico occidentale in tale lista, questo algoritmo è spesso chiamato algoritmo di Sollin, specialmente nella letteratura del computing parallelo.