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 84
- Downloads 0
Detection and Prevention of Gray Hole and Black Hole Attack in MANET
An Ad hoc network is the network with no fixed infrastructure. There is no central administrator so any node can come and move in and outside of the network in a dynamic manner. This makes it more dynamic and complex whi...
Morphology of Koch Fractal Antenna
Antenna is paramount element for the radio communication entity using radio frequency and microwaves. In twenty-first century wireless communication systems, there is a demand for wider bandwidth, multiband and low pro...
STUDY OF INCREASE IN GLOBAL COMPONENTS IN HYBRID WAVELETS ON DATA COMPRESSION
This paper presents a hybrid wavelet transform technique which studies the effect of global components on the quality of image compression. Hybrid wavelet transform is generated using two different component orthogonal t...
A comparative study of chain based routing algorithms in wireless sensor networks
Many routing algorithms for Wireless Sensor Networks (WSNs) are designed and presented in the literature. The main target of these algorithms is to improve the performance of WSNs. In this paper, a comparative study of c...
PERFORMANCE ANALYSIS OF EFFECT RATE OF CROSS LAYER BASED INTRUSION DETECTION FOR WIRELESS LAN
Wireless ad-hoc networks are vulnerable to various kinds of security threats and attacks due to relative ease of access to wireless medium and lack of a centralized infrastructure. Security is an alarming concern, as eve...