Room 327

Verifying minimum spanning trees in linear time

Aditi Dudeja

IMSc Chennai

Given an edge weighted undirected graph, and a spanning tree of the graph, we give linear time algorithms that will verify whether the given spanning tree is a minimum spanning tree of the graph. The algorithm and the implementation are based on the following papers:

1. A simpler minimum spanning tree verification algorithm by V. King, Algorithmica 1997, and

2. An even simpler linear-time algorithm for verifying minimum spanning trees by Torben Hagerup WG 2009