Study of Shortest Path And Minimum Spanning Tree Problems

Abstract

Title of the thesis Study of Shortest Path and Minimum Spanning newlineTree Problems . newlineThe content of this thesis encompasses two very significant, extensively studied, newlineand widely applied problems involving Graph Theory and Computer Science, newlinenamely The Shortest Path Problem and The Minimum Spanning Tree Problem . newlineThis thesis consists of nine chapters. One chapter, i.e. Chapter 2 is devoted for newlinethe study of the concept of connected components of graphs and develop an newlinealgorithmic scheme to obtain the connected components of undirected graphs. As newlinewe mostly deal with the connected graphs in our study, a comprehensive idea on newlineconnected components will help us understand the topics of the subsequent newlinechapters. Five chapters, i.e. Chapter 3 to Chapter 7 involve the study of Shortest newlinePath Problem, whereas the remaining two chapters, i.e. Chapter 8 and Chapter 9 newlineexplore on Minimum Spanning Tree Problem. newlineIn Chapter 2 we develope a polynomial-time approximation scheme algorithm for newlineobtaining connected components of an undirected graph using adjacency matrix newlineassociated with it. We further supplement our algorithm with one example and newlinedemonstrate its programming implementation using C++ programming. newline