To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
NAMST-A: New Algorithm for Minimum Spanning Tree (Adaptive) using Reconfigurable Logic |
|
Author |
Prasad G. R., K. C. Shet, Narasimha B. Bhat |
| Citation |
Vol. 8 No. 5 pp. 187-194 |
|
Abstract |
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. |
|
Keywords |
Reconfigurable computing, minimum spanning tree, ball and string model, FPGA |
|
URL |
