A novel approach for constructing a minimum spanning tree

Abstract

The spanning tree of a graph is obtained when all vertices of a graph are connected in such a way that no cycle is formed. This work proposes a new algorithm that, at each round, selects a maximal independent set of vertices (an inclusion-maximal, not necessarily maximum-cardinality, set of pairwise non-adjacent vertices) and attaches to every vertex of that set its cheapest cycle-safe incident edge to find a minimum spanning tree of any weighted graph. The procedure organizes safe-edge selections into batches indexed by maximal independent sets; its number of such batching rounds depends on the maximal independent sets selected, and this notion of a round is not directly comparable to a single iteration of Prim's or Kruskal's algorithm without further definition. Using the classical cut property, we prove that the procedure always produces a minimum spanning tree of a connected graph. If r denotes the number of independent-set rounds, a straightforward sequential implementation has worst-case running time O(r(n+m)+m log m). We do not claim, and this paper does not prove, that the number of rounds is minimized over all possible choices of maximal independent sets, nor that the resulting sequential running time improves on the classical O(m log n) bounds. This work may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.