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

http://paper.ijcsns.org/07_book/200805/20080528.pdf