Borůvka's algorithm
Algoritmo de Boruvka
- Date
- 1926 · confidence high
- Place
- Brno, Moravia, Czechia
- Credited to
- Otakar Borůvka
- Field
- Knowledge & symbols
What it is
A greedy algorithm for finding the minimum spanning tree of a graph, published by Otakar Borůvka as a method for designing an efficient electricity network in Moravia.
What it led to
- Efficient design of electrical distribution networks
- Parallel minimum-spanning-tree algorithms
- Later rediscoveries (Sollin, Florek et al.)
- Basis for modern distributed graph algorithms