A new algorithm for the minimum spanning tree verification problem

Matthew Williamson () and K. Subramani ()

Computational Optimization and Applications, 2015, vol. 61, issue 1, 189-204

Abstract: This paper proposes a new algorithm for the minimum spanning tree verification (MSTV) problem in undirected graphs. The MSTV problem is distinct from the minimum spanning tree construction problem. The above problems have been studied extensively, and there exist several papers in the literature devoted to them. Our algorithm for the MSTV problem combines the insights of Borůvka’s algorithm for constructing a minimum spanning tree with a bucketing scheme. The principal idea underlying this combination is the efficient identification of edges that cannot be part of any minimum spanning tree. Although the proposed algorithm imposes no restrictions on the input graph, it was designed to exploit the case in which the number of distinct edge weights is small. On a graph with $$n$$ n vertices, $$m$$ m edges, and $$K$$ K distinct edge weights, our algorithm runs in $$O(m+n\cdot K)$$ O ( m + n · K ) time. It follows that our algorithm runs in linear time if $$K$$ K is a fixed constant. Although there exist several linear time MSTV algorithms in the literature, our algorithm improves on the state of the art in two ways, viz., it is conceptually simpler, and it is easy to implement. We contrast the performance of our algorithm vis-à-vis Hagerup’s linear time MSTV algorithm, which is one of the more practical linear-time MSTV algorithms. Our experiments indicate that the proposed algorithm is superior to Hagerup’s algorithm when $$K \le 24$$ K ≤ 24 . One surprising observation is that our algorithm is substantially faster than Hagerup’s algorithm on “No” instances, i.e., on instances in which the input spanning tree is not the minimum spanning tree. Copyright Springer Science+Business Media New York 2015

Keywords: Minimum spanning tree; Verification; Graph theory; Depth-first Search; Certification (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-014-9702-8 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:61:y:2015:i:1:p:189-204

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-014-9702-8

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().