AN APPROACH TO GENERATE MST WITHOUT CHECKING CYCLE
Journal Title: INTERNATIONAL JOURNAL OF COMPUTERS & TECHNOLOGY - Year 2013, Vol 4, Issue 2
Abstract
Abstract: A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. MST generation is a NP hard problem. Now this paper represents an algorithm to find minimum spanning tree without checking cycle. Good time and space complexities are the major concerns of this algorithm. Running Time (complexity) of this algorithm = O(E*log V) (E = edges, V = nodes),which is obviously better than prim’s algorithm(complexity- E +Vlog V) .  This algorithms operate at O(E * log(V)) time, though Prim’s can be optimized to O(E + V log V) by using specialized data structures(heap). For large graphs, these algorithms can take significant amount of time to complete. This algorithm is important in many real world applications. One example is an internet service provider determining the best way to install underground wires in a neighbourhood in order to use the least amount of wire and dig the least amount of ground.
Authors and Affiliations
Sharadindu Roy, Prof. Samar Sen Sarma
Keywords
Related Articles
- EP ID EP649979
- DOI 10.24297/ijct.v4i2b1.3229
- Views 75
- Downloads 0
Multi-factor analysis of pair programming based on PSP methodology
In regard with designing software, users play key role. In order to design software, it is necessary to observe standard principles of designation, using templates and using modern methods. Over the decades, using...
Knowledge based System for Improving Design and Manufacturing Processes for Electrochemical MachiningIn Computer based Concurrent Engineering
The traditional design of product, the preceding constraints and limitations are considered sequentially. In order to reduce the product development cycle time and cost and increase quality and productivity, concurrent (...
Artificial Intelligent techniques for Flow Bottom Hole Pressure Prediction
This paper proposes Radial Basis and Feed-forward Neural Networks to predict the flowing bottom-hole pressure in vertical oil wells. The developed neural network models rely on a large amount of available historical data...
ONTOLOGY BASED CLASSIFICATION AND CLUSTERING OF RESEARCH PROPOSALS AND EXTERNAL RESEARCH REVIEWERS
With the rapid development of research work in projects, research project selection is a necessary task for the research funding agencies. It is common to group the large number of research proposals, received by the res...
Two Modified Hager and Zhang's Conjugate Gradient Algorithms For Solving Large-Scale Optimization Problems
At present, the conjugate gradient (CG) method of Hager and Zhang (Hager and Zhang, SIAM Journal on Optimization, 16(2005)) is regarded as one of the most effective CG methods for optimization problems. In order to furth...