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 93
- Downloads 0
Secure SDN Framework for Data Exfiltration via Video Steganography
The popularity of steganography in the data exfiltration of private corporate sensitive data is increased. So it is important to detect such malicious activity. Becausethe data being transferred can hide the large amount...
Twig Pattern Minimization Based on XML Schema Constraints
Twig pattern is one of the core components of XQuery. Twig usually includes redundancy nodes which can be optimized. Schema feature is used to judge whether the node of Twig pattern is redundancy. In this paper, we propo...
Performance of BAT Algorithm on Localization of Wireless Sensor Network
Many applications of wireless sensor networks (WSN) require information about the geographical location of each sensor node. Devices that form WSN are expected to be remotely deployed in large numbers in a sensing field,...
Hybrid Scheduling Scheme for Real Time Systems
Systems as asymmetric multiprocessor platforms are considered power-efficient multiprocessor architectures, efficient task partitioning (assignment) and play a crucial role in achieving more energy efficiency at these mu...
ARTFSC Average Relative Term Frequency Sentiment Classification
Sentiment Classification refers to the computational techniques for classifying whether the sentiments of text are positive or negative. Statistical Techniques based on Term Presence and Term Frequency, using Support Vec...