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

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

Ζώρος Δημήτριος (EL)

born_digital_postgraduate_thesis

Διπλωματική Εργασία (EL)

Postgraduate Thesis (EN)

2014

Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους. (EL)

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. (EN)

Greek

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

Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών

https://creativecommons.org/licenses/by-nc/4.0/

University of Athens

Pergamos Digital Library

Postgraduate Thesis