Vol. 2, No. 4, 2009

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

Volume 10
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

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
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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