Can a minimum spanning tree be constructed by processing several non-adjacent vertices together rather than selecting one vertex or edge at a time?
This study proposes a new algorithm for constructing a minimum spanning tree of a connected weighted graph.
At each round, the method selects a maximal independent set of pairwise non-adjacent vertices and connects each selected vertex using its cheapest incident edge that does not create a cycle.
By organising these safe-edge selections into batches, the algorithm processes several vertices within the same round instead of following the one-at-a-time approach used by classical methods such as Primโs and Kruskalโs algorithms.
The researchers prove the correctness of the proposed method using the classical cut property, showing that the procedure always produces a minimum spanning tree for a connected weighted graph.
The number of batching rounds depends on the maximal independent sets selected during the process.
For a straightforward sequential implementation, the algorithm has a worst-case running time of O(r(n + m) + m log m), where r represents the number of independent-set rounds.
The authors emphasise that the study does not claim that the number of rounds is always minimised or that the proposed sequential implementation is faster than the classical O(m log n) bounds associated with established minimum spanning tree algorithms.
Instead, the approach introduces a different way of organising safe-edge selections by processing groups of mutually non-adjacent vertices together.
The proposed method may be useful in large weighted-network applications, including communication networks, wiring connections, and transportation networks.
๐ Read the full article here:
https://doi.org/10.46481/jnsps.2026.3739
Published in: Journal of the Nigerian Society of Physical Sciences