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

Nešetřil, Jaroslav; Milková, Eva; Nešetřilová, Helena

Discrete Math. 233, No. 1-3, 3-36 (2001).

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.

Reviewer: Roman Duda (Wrocław)

MSC:

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

Citations:

Zbl 0998.68003