To search, Click below search items.


All Published Papers Search Service


NAMST-A: New Algorithm for Minimum Spanning Tree (Adaptive) using Reconfigurable Logic


Prasad G. R., K. C. Shet, Narasimha B. Bhat


Vol. 8  No. 5  pp. 187-194


This paper presents NAMST-A (New Algorithm for Minimum Spanning Tree- Adaptive), a new reconfigurable logic based algorithm for finding minimum spanning tree (MST). It is an extension of NAMST [7]. It uses ball and string model, and has a time complexity O(N), where ‘N’ is the number of nodes. It is faster compared to other existing MST algorithms as it does not need to find the minimum of nodes/adjacent nodes. On Xilinx Virtex II Pro kit, NAMST-A takes 428.92 ns for finding MST of size 28 in a graph of 17 nodes.


Reconfigurable computing, minimum spanning tree, ball and string model, FPGA