Unit:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Supervisors info:
Αναπλ. Καθηγητής Δημήτριος Μ. Θηλυκός (επιβλέπων), Καθηγητής Ελευθέριος Κυρούσης, Αναπλ. Καθηγητής Σταύρος Κολλιόπουλος
Original Title:
Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των
Translated title:
Obstructions and Algorithms for Graph Searching Problems
Summary:
Graph Searching is a field of Discrete mathematics with numerous applications
in many areas of Theoretical Computer Science. It Is also of great theoretical
interest as it formalizes many important combinatorial problems. We present the
motivations which led researchers to graph searching, we typically define the
three basic types of searching, and we introduce some of the major variants.
Then we analyze the concepts of monotonicity and connectivity and record some
results from the literature. Next we study the Theory of Partial Orders on
graph classes and how this is associated with the characterization of some
classes through a set of forbidden graphs, called obstruction Set of the class.
After briefly mentioning the necessary concepts, we present all so far known
obstruction sets for classes of graphs with bounded search number. The larger
set to be mentioned is included in the results of our work, which is still
under preparation. Graph searching is closely related to the Width Parameters
of a graph. Most of the results in the literature concern these parameters, as
their terminology eases the proofs of the theorems. In Chapter 6 we define some
important width parameters and we illustrate how they relate to the search
number of the graph. The third part of this work consists of the study of the
Computational Complexity of some graph searching problems. Finally we make a
brief presentation of our results and the core ideas underlying their proofs.
Keywords:
Obstruction sets, Graph Searching, Algorithms, Discrete Mathematics, Graph Theory
Number of index pages:
iii-iv
