My idea behind this research is to find a new
greedy way to find the optimal solution in Euclidean
space .Today we face many real life complex problems, to
solve real life of complex problem we developed a new
greedy approach in minimum time. Here we have find the
time complexity of algorithm (Kruskal, Prims, Dijkastra,
Tsp) and have compared following algorithms with each
other. Our main goal to find the best case time complexity
for both Minimum Spanning Tree (MST) and Single Source
Shortest Path (SSST).Both Approaches MST and SSSP have
been used in greedy approach. In this research paper, we
have developed same way for same approach with reduced
time complexity which provides best case time complexity
for any weighted graph in Euclidean space. We have
developed an algorithm that manipulates the greedy
approach for a set of n points in a metric space with
corresponding doubling dimension. Suppose G (V, E, w) is a
simple graph where V denotes a set of Vertices in a given
graph and E denotes set of edges of a graph and vertices are
connected with edges. All edges having non negative weight
which also represent distance between two nodes in a given
graph. To remember greedy approach as we developed a
new greedy approach to find the shortest route among nodes
or vertices. Which gives an optimal way in minimum time
among nodes or vertices? Here we have worked the concept
of MST and SSSP. Simply this research is based on
combinatorial optimization and focused to find the optimum
solution of various types of general problems.
Published In : IJCAT Journal Volume 2, Issue 7
Date of Publication : July 2015
Pages : 227 - 231
Figures :07
Tables : --
Publication Link :Analysis The Time Complexity of Greedy
Algorithm Used in Optimization
Yogesh Chanchal : has done B.Tech in
computer science stream from Uttar Pradesh
Technical university. I have 1 year teaching
experience from somany institute of
Technology and management college,
Rewari , Haryana. Now I am pursuing
M.Tech in computer science stream at
Teerthanker Mahaveer University Moradabad
Dr. Asherdra Kumar Saxena : has done Ph.D. in
the area of applied mathematics from MJP
Rohilkhand University, Bareilly. I completed M.Phill
in computer Science from Alagappa University
Tamilnadu and MCA degree from Uttar Pradesh
Technical University Lucknow in 2003. I completed
M.Sc. in Mathematics from MJP Rohilkhand
University, Bareilly in 1997. I am working in
Teerthanker Mahaveer University, Moradabad
(U.P.), from July 2003 to till date. At present, I am
Associate Professor & HOD in College of
Computing Sciences and Information Technology,
Teerthanker Mahaveer University, Moradabad
(U.P.). I have 12 years of experience in teaching,
administration. I have published 15 papers in
International Journals / Conferences and 10 papers
in National Journal / Conferences. My research
interest includes solving the different problems in
networks using Optimization Techniques,
Algorithm design and reducing the complexity of
algorithms.
Greedy Algorithms
Greedy Approaches
Minimum Spanning Tree
Single Source Shortest Path
mobile communication
Approximate Solutions
Time Complexity
The yTSP and yKRUSKAL exists at the top of our
Operational Research. Both algorithms describe many
practical applications and its study over the many years or
so has led to important theoretical developments.
Problems having a few numbers of vertices can now be
solved routinely to optimality. Instances involving more
than 100s of vertices have also been solved exactly by
means of constraint yTSP and yKRUSKAL algorithms. A
number of important heuristics also proposed both search
methods and generalized insertion algorithms appear to
hold much potential.
[1] I. Althofer, G. Das, D. P. Dobkin, D. Joseph, and J.
Soares. On sparse spanners of weighted graphs.
Discrete and Computational Geometry, 9(1):81–100,
1993.
[2] P. B. Callahan and S. R. Kosaraju. A decomposition of
multidimensional point sets with applications to knearest-
neighbors and n-body potential fields. Journal
of the ACM, 42:67–90, 1995.
[3] B. Chandra. Constructing sparse spanners for most
graphs in higher dimensions. Information Processing
Letters, 51(6):289–294, 1994.
[4] B. Chandra, G. Das, G. Narasimhan, and J. Soares.
New sparseness results on graph spanners.
International Journal of Computational Geometry and
Applications, 5:124– 144, 1995.
[5] L. P. Chew. There is a planar graph almost as good as
the complete graph. In SCG ’86: Proceedings of the
2nd Annual ACM Symposium on Computational
Geometry, pages 169–177, 1986.
[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C.
Stein. Introduction to Algorithms. MIT Press and
McGraw-Hill, 2nd edition, 2001.
[7] G. Das, P. J. Hagerman, and G. Narasimhan.
Optimally sparse spanners in 3-dimensional Euclidean
space. In SCG’93: Proceedings of the 9th Annual
ACM Symposium on Com- putational Geometry,
pages 53–62, 1993.
[8] G. Das and G. Narasimhan. A fast algorithm for
constructing sparse Euclidean spanners. International
Journal of Computational Geometry and Applications,
7:297–315, 1997.
[9] E. W. Dijkstra. A note on two problems in connection
with graphs. Numeric Mathematics, 1:269–271, 1959.
[10] D. Eppstein. Spanning trees and spanners. In J.-R.
Sack and J. Urrutia, editors, Hand- book of
Computational Geometry, pages 425–461. Elsevier
Science Publishers, Amster- dam, 2000.