الفهرس 
Some Graph TerminologiesOnly 14 pages are availabe for public view
 |  | from | 158 |  |  |
| | | from | 158 | | |
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].