Improvement on prim’s MST based algorithm using multi-element heap nodes.

Muhammad Uzair; Anwar Majid Mirza; Nisar Ahmed Memon

No Detail Found!

Improvement on prim’s MST based algorithm using multi-element heap nodes.

Author(s)

Muhammad Uzair National Development Complex, Islamabad, Pakistan

Anwar Majid Mirza Faculty of Computer Science and Engineering, Ghulam Ishaq Khan GIK Institute of Engineering Sciences and Technology, Topi, Sawabi, Peshawar, Pakistan

Nisar Ahmed Memon Department of Computer Systems Engineering, Quaid-e-Awam University of Engineering, Sciences and Technology, Nawabshah, Pakistan

Abstract

This paper suggests an improvement on the problems of image segmentation using graph based technique in comparison to previous results. The two algorithms are similar in that they both use the same framework for segmentation, i.e. both use MST (Minimum Spanning Tree) algorithms, but out of the two, one is based on Kruskal’s algorithms for finding minimum spanning trees while the other one is based on Prim’s algorithm for minimum spanning trees. The results of the comparison showed that Prim based technique is more flexible but much slower as compared to the Kruskal based technique. A novel idea of a heap with multi element nodes is then proposed to speed up the Prim based technique. The results of using a heap with multi element nodes are quite promising. The new implementation of the Prim based technique retains all the desirable features and yet gives a running time that is comparable to that of Kruskal based technique.

Publication Details

Page(s) 29-40

DOI DOI not available

Published Journal: Mehran University Research Journal of Engineering and Technology, Volume: 25, Issue: 1, Year: 2006

Request the full text from PASTIC

Citations

Downloads

Views