Postgraduate Thesis uoadl:1319352 57 Read counter

Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και Υπολογισμού

Library of the School of Science

Library of the School of Science

2014-02-04

2014

Ζώρος Δημήτριος

Αναπλ. Καθηγητής Δημήτριος Μ. Θηλυκός (επιβλέπων), Καθηγητής Ελευθέριος Κυρούσης, Αναπλ. Καθηγητής Σταύρος Κολλιόπουλος

Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των

Greek

Obstructions and Algorithms for Graph Searching Problems

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.

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.

Obstruction sets, Graph Searching, Algorithms, Discrete Mathematics, Graph Theory

Yes

iii-iv

Yes

49

iv, 68