الفهرس | Only 14 pages are availabe for public view |
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. In Chapter two, we deal with a special case of the matching problem, called Euclidean minimum weighted perfect matching problem. A new algorithm (RPMalgorithm) for solving this problem is proposed. The suggested algorithm is simple and does not depend on the geometric nature of the input graph. So, this algorithm can be applied on any weighted graph. The algorithm gives an -approximation solution with probability at least 1/2. Chapter three is devoted to treat a special case of the Set Cove Problem (SCP). This problem is NP-complete, so there is no polynomial algorithm for solving this problem. The main aim of this chapter is to introduce a new approximation algorithm (ASC-algorithm) for this special case of SCP (k-SCP, . The suggested algorithm computes an approximation solution for the underlying problem. The ratio of this approximation algorithm is which is better than the previous ones. Chapter four gives a treatment of two related problems which are the independent set and vertex cover on a special type of graphs. On this type of graphs, the two problems are NP-complete. The goal of this chapter is to propose an approximation algorithm (AIS-algorithm) for the maximum vii independent set problem on bounded -degree graphs, where is the maximum degree of vertices, . This algorithm is based on the concept of a one-separated collection of subsets of vertices in graphs. The algorithm gives a -approximation. So, this algorithm improves the approximation ratio of previous algorithms for this problem. By using the designed approximation algorithm for the maximum independent set problem on bounded - degree graphs, we obtain an approximation algorithm for the minimum vertex cover problem on the same class of graphs with an approximation ratio . In the appendix, the implementations of the introduced algorithms using Java programming language are given. In A.1, the implementation of RPM-algorithm is presented. In A.2, the implementation of ASC-algorithm is introduced. Finally, AIS-algorithm is implemented in A.3. All results of Chapter 2 and 3 are original. Those of the former being accepted by IJACSA[1]. While those of the later are published in AJSE[27]. |