On Heuristic Algorithms for Some Graph Theory Problems

Abstract

The last few decades have witnessed a tremendous growth in the area of using the solutions of some problems in the graph theory in many important fields, e.g., operations research, statistics, combinatorics, computational geometry. Because most of these problems belong to the class NP-complete, so several researchers use the heuristic, approximation, and randomized approaches. These approaches have ability to find the near-optimal solutions. Moreover, they help researchers to improve the solutions of some problems and applying them in real problems such as shape matching, network security, information retrieval, computer vision, and other important real life situations. The thesis deals with three problems in graph theory. These problems are special cases of matching problem, set cover problem, and independent set and vertex cover problems. The matching problem can be solved in polynomial-time. Many real-world applications of this problem require graphs of such large size that the running time of the fastest available algorithm is too cost. So, several researchers did more efforts to find good approximation algorithms for the matching problem which are faster and simpler than the optimal algorithms. The special cases of the two others problems are still NPcomplete like the original ones. The thesis consists of four chapters, conclusion, one appendix, and a list of relevant references. vi Chapter one includes the necessary background material. A brief introduction to the graph theory and probability theory that are relevant to the thesis, are given. Also, some fundamentals of algorithms and the complexity measures for deterministic and randomized algorithms are presented. Furthermore, an introduction of some types of algorithms, e.g., heuristic, approximation, and randomized algorithms, is given.