Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history. (English) Zbl 0999.01019

Early in the 20th century there appeared the following minimum spanning tree problem (for its early history, see R. L. Graham and P. Hell [Ann. History Comput. 7, No. 1, 43-57 (1985; Zbl 0998.68003)]; the formulation of the problem is modern): Given a connected graph with real weights assigned to its edges, find a spanning tree with the minimal weight. The problem has been solved by O. Borůvka (1899-1996) in 1926 [Práce Moravské Přírodovědecké Společnosti Brno 3, 37-58 (1926)] and this paper provides an English translation of his two works on it (originally in Czech), followed by remarks on its further development and by a short biography of Borůvka. The bibliography is extensive and consists of 51 items.


01A60 History of mathematics in the 20th century
01A75 Collected or selected works; reprintings or translations of classics
90C27 Combinatorial optimization
90-03 History of operations research and mathematical programming

Biographic References:

Borůvka, O.


Zbl 0998.68003
Full Text: DOI