Vol. 2, No. 4, 2009

Download this article
Download this article For screen
For printing
Recent Issues

Volume 15
Issue 2, 185–365
Issue 1, 1–184

Volume 14, 5 issues

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Author Index
Coming Soon
Other MSP Journals
Minimum spanning trees

Pallavi Jayawant and Kerry Glavin

Vol. 2 (2009), No. 4, 439–450

The minimum spanning tree problem originated in the 1920s when O. Borůvka identified and solved the problem during the electrification of Moravia. This graph theory problem and its numerous applications have inspired many others to look for alternate ways of finding a spanning tree of minimum weight in a weighted, connected graph since Borůvka’s time. This note presents a variant of Borůvka’s algorithm that developed during the graph theory course work of undergraduate students. We discuss the proof of the algorithm, compare it to existing algorithms, and present an implementation of the procedure in Maple.

minimum spanning tree, graph algorithm, graph theory, Maple
Mathematical Subject Classification 2000
Primary: 05C85, 68R10
Received: 1 March 2009
Accepted: 2 May 2009
Published: 28 October 2009

Communicated by Arthur T. Benjamin
Pallavi Jayawant
Department of Mathematics
Bates College
Lewiston, ME 04240
United States
Kerry Glavin
Department of Mathematics
Bates College
Lewiston, ME 04240
United States