Browse Prior Art Database

On the History of the Minimum Spanning Tree Problem

IP.com Disclosure Number: IPCOM000129464D
Original Publication Date: 1985-Jan-01
Included in the Prior Art Database: 2005-Oct-06
Document File: 14 page(s) / 56K

Publishing Venue

Software Patent Institute

Related People

R. L. GRAHAM: AUTHOR [+3]

Abstract

It is standard practice among authors discussing the minimum spanning tree problem to refer to the work of Kruskal (1956) and Prim (1957) as the sources of the problem and its first efficient solutions, despite the citation by both of Boruvka (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 shall explore and compare these works and their motivations, and relate them to the most recent advances on the minimum spanning tree problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Copyright ©; 1985 by the American Federation of Information Processing Societies, Inc. Used with permission.

On the History of the Minimum Spanning Tree Problem

R. L. GRAHAM

PAVOL HELL

(Image Omitted: © 1985 by the American Federation of Information Processing Societies. Inc. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage. the AFIPS copyright notice and the title of the publication and its date appear, and notice is given that the copying is by permission of the American Federation of Information Processing Societies, Inc. To copy otherwise, or to republish, requires specific permission. Authors' Addresses: R. L. Graham, Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ 07974. P. Hell, Department of Computing Science,

Simon Fraser University, Burnaby, British Columbia V5A lS6. © 1985 AFIPS 0164- 0239/85/010043-057

On the History of the Minimum Spanning Tree Problem

R. L. GRAHAM

PAVOL HELL .00/00)

It is standard practice among authors discussing the minimum spanning tree problem to refer to the work of Kruskal (1956) and Prim (1957) as the sources of the problem and its first efficient solutions, despite the citation by both of Boruvka (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 shall explore and compare these works and their motivations, and relate them to the most recent advances on the minimum spanning tree problem.

Categories and Subject Descriptors: G 2.2 [Discrete Mathematics]: Graph Theory -- trees; E. 1 [Data Structures] -- trees; K.2 [History of Computing] -- software General Terms: Algorithms, Theory Additional Key Words and Phrases: minimum spanning tree

Introduction

The minimum spanning tree problem (MSTP) is one of the most typical and well-known problems of combinatorial optimization; methods for its solution, though simple, have generated important ideas of modern combinatorics and have played a central role in the design of computer algorithms [AhHoU174], [ReNiDe77], [Chr75], [HorSah78].11 The problem is typically stated as follows.

(Image Omitted: Given such a weighted graph [a graph G, whose nodes represent cities, whose edges represent possible communication links, and whose edge weights represent the costs of

1 1 In this paper, References are shown in the preceding way in the text and are alphabetized by the abbreviations shown in brackets.

IEEE Computer Society, Jan 01, 1985 Page 1 IEEE Annals of the History of Computing Volume 7 Number 1, Pages 43-57

Page 2 of 14

On the History of the Minimum Spanning Tree Problem

  construction, or the lengths of the links] one would then wish to select for construction a set of communication links that would connect...