Vol. 2, No. 4, 2009

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

Volume 11
Issue 3, 361–540
Issue 2, 181–359
Issue 1, 1–179

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
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Minimum spanning trees

Pallavi Jayawant and Kerry Glavin

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

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.

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

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