{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1319352"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1319352","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των","abstract":"Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους.","abstract_html":"Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους.","abstract_has_math":false,"creators":["Ζώρος Δημήτριος"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014","date_published":"2014","updated_at":"2026-11-19T05:25:45Z","subjects":[],"languages":["Ελληνικά","Greek"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319352"],"render_values":[{"text":"uoadl:1319352","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319352","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1319352","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1319352","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ζώρος Δημήτριος"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["Ελληνικά","Greek"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1319352","https://pergamos.lib.uoa.gr/uoa/dl/object/1319352"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους.","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."]},{"key":"dc:title","label":"Title","values":["Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των"]}]}],"canonical_facts":{"dc:creator":["Ζώρος Δημήτριος"],"dc:date":["2014"],"dc:description":["Η Ανιχνευση Γραφηματων αποτελει εναν κλαδο των Διακριτων Μαθηματικων με πληθος εφαρμογων σε πολλους τομεις της Θεωρητικης Πληροφορικης. Παρουσιαζει επισης μεγαλο θεωρητικο ενδιαφερον καθως μεσω αυτης εκφραζονται πολλα σημα- ντικα συνδυαστικα προβληματα. Στα πρωτα κεφαλαια αυτης της εργασιας θα παρουσιασουμε τα κινητρα που ωθη- σαν τους ερευνητες να ασχοληθουν με την ανιχνευση γραφηματων, θα ορισουμε τυπικα τους τρεις βασικους τυπους της και θα παρουσιασουμε τις σημαντικοτερες παραλλαγες τους. Στη συνεχεια θα αναλυσουμε τις εννοιες της μονοτονιας και της συνεκτικοτητας και θα καταγραψουμε μερικα αποτελεσματα απο τη βιβλιογραφια. Το δευτερο σκελος της εργασιας αυτης ειναι η μελετη της Θεωριας Μερικων Δια- ταξεων σε κλασεις γραφηματων και πως απο αυτη προκυπτει ο χαρακτηρισμος της κλασης μεσω ενος συνολου απαγορευμενων γραφηματων, το οποιο καλειται Συνολο Παρεμποδισης της κλασης. Αφου αναφερουμε συνοπτικα τις απαραιτητες εννοιες, θα παρουσιασουμε ολα τα εως τωρα γνωστα συνολα παρεμποδισης για κλασεις γραφημα- των με φραγμενο αριθμο ανιχνευσης. Το μεγαλυτερο σε μεγεθος συνολο που θα ανα- φερθει συγκαταλεγεται στα αποτελεσματα δικης μας εργασιας, που βρισκεται ακομα υπο συγγραφη. Η ανιχνευση γραφηματων συνδεεται αρρηκτα με τις Παραμετρους Πλατους γρα- φηματος. Τα περισσοτερα αποτελεσματα της βιβλιογραφιας αφορουν τις παραμετρους αυτες καθως η ορολογια τους διευκολυνει αρκετα την αποδειξη των θεωρηματων. Στο Κεφαλαιο 6 θα ορισθουν οι σημαντικοτερες παραμετροι πλατους γραφηματος και θα παρουσιαστει ο τροπος που σχετιζονται με τους αριθμους ανιχνευσης. Το τριτο σκελος της εργασιας αυτης αφορα την Υπολογιστικη Πολυπλοκοτητα των προβληματων ανιχνευσης γραφηματων. Στο τελος της εργασιας αυτης θα κανουμε μια συνοπτικη παρουσιαση των δικων μας αποτελεσματων και των κεντρικων ιδεων που διεπουν την αποδειξη τους.","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."],"dc:identifier":["uoadl:1319352","https://pergamos.lib.uoa.gr/uoa/dl/object/1319352"],"dc:language":["Ελληνικά","Greek"],"dc:title":["Παρεμποδι?σεις και Αλγο?ριθμοι για Προβλη?ματα Ανι?χνευσης Γραφημα?των"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:25:45Z"}