Minimum spanning trees

Jayawant, Pallavi; Glavin, Kerry

doi:10.2140/involve.2009.2.439

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Minimum spanning trees

Pallavi Jayawant and Kerry Glavin

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

DOI: 10.2140/involve.2009.2.439

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

Vol. 2, No. 4, 2009