On the history of the minimum spanning tree problem. (English) Zbl 0998.68003

Graham, R. L.; Hell, Pavol

Ann. Hist. Comput. 7, No. 1, 43-57 (1985).

Summary: It is standard practice among authors discussing the minimum spanning tree problem to refer to the work of J. B. Kruskal [Proc. Am. Math. Soc. 7, 48-5- (1956; Zbl 0070.18404)] and R. C. Prim [Bell Syst. Tech. J. 36, No. 6, 1389-1402 (1957)] as the sources of the problem and its first efficient solutions, despite the citation by both of O. Borůvka [Práce Moravske Přírod. Společnosti Brno 3, 37-58 (1926)] as a predecessor. In fact, there are several apparently independent sources and algorithmic solutions of the problem. They have appeared in Czechoslovakia, France, and Poland, going back to the beginning of this century. We explore and compare these works and their motivations, and relate them to the most recent advances on the minimum spanning tree problem.

MSC:

68-03	History of computer science
01A60	History of mathematics in the 20th century
90-03	History of operations research and mathematical programming
90B10	Deterministic network models in operations research

Citations:

Zbl 0070.18404