MSc thesis defense presentation
Dimitris Zoros defends his MSc thesis
| Date: | Tuesday, 04 Feb 2014 |
|---|---|
| Time: | 10:00-11:00 |
| Location: | Univeristy of Athens, Department of Mathematics, University of Athens, room A11 |
| Thesis title: | Obstructions and Algorithms for Graph Searching Problems |
| Committee: |
Παρουσίαση Διπλωματική Εργασίας του Μ.Π.Λ.Α.,
Ο Δημήτρης Ζώρος, μεταπτυχιακός φοιτητής του ΜΠΛΑ, θα παρουσιάσει την Διπλωματική του εργασία, την Τρίτη 04/01/2013 και ώρα: 10:00 στην Αίθουσα 11.
Το θέμα είναι «Παρεμποδίσεις και Αλγόριθμοι για Προβλήματα Ανίχνευσης σε Γραφήματα»
Thesis abstract
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.