Παρεμποδίσεις και αλγόριθμοι για προβλήματα διατάξεων σε γραφήματα

Περίληψη

Η σύγχρονη Θεωρία Γραφημάτων έχει επηρεαστεί σε μεγάλο βαθμό από την δουλειά των N. Robertson και P. Seymour. έσα από αυτήν, πληθώρα από δομικά, συνδυαστικά, καθώς και αλγοριθμικά αποτελέσματα εισήχθηκαν, σε μία σειρά από εργασίες που είχε απώτερο στόχο την απόδειξη της εικασίας του Wagner. Σε αυτή την διδακτορική διατριβή επικεντρωνόμαστε στην μελέτη των Συνόλων Παρεμπόδισης, μία από τις σημαντικότερες συνδυαστικές έννοιες αυτής της θεωρίας. Πιο συγκεκριμένα, μελετάμε την συνδυαστική και αλγοριθμική πτυχή, καθώς και την υπολογισιμότητα, των γραφημάτων παρεμπόδισης, σε σχέση με παραμέτρους γραφημάτων που πηγάζουν από Διατάξεις σε Γραφήματα, Προβλήματα Διαγραφής ορυφών και Προβλήματα Ανίχνευσης Γραφημάτων. Η μελέτη αυτή είναι βασισμένη σε σχέσεις μερικής διάταξης γραφημάτων, όπως τα ελάσσονα, οι εμβυθίσεις και οι συνθλίψεις. Η μελέτη μας περιλαμβάνει αποτελέσματα σχετικά με την ύπαρξη και υπολογισιμότητα των συνόλων παρεμπόδισης, συνδυαστικά φράγματα στο μέγεθος τους, καθώς και την αλ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

Modern Graph Theory is heavily influenced by the seminal work of N. Robertson and P. Seymour, known as Graph Minors. Through this work, a wealth of structural, combinatorial, as well as algorithmic, results has been introduced, in a series of papers having as ultimate goal to give an affirmative answer to Wagner’s Conjecture. In this doctoral thesis we focus on the study of Obstruction Sets, one of the most important combinatorial concepts of this theory. In particular, we study the combinatorics and the algorithmic and computability aspects of graph obstructions and their relation to graph parameters emerging from Graph Layouts, Vertex Deletion Problems, and Graph Searching Problems. We consider several partial ordering relations on graphs such as minors, immersions, and contractions. Our study includes results on the existence and the computability of obstruction sets, combinatorial bounds on their size, and their interplay with parameterized complexity and kernelization.

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/41215
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/41215
ND
41215
Εναλλακτικός τίτλος
Obstructions and algorithms for graph layouts problems
Συγγραφέας
Ζώρος, Δημήτριος (Πατρώνυμο: Γεώργιος)
Ημερομηνία
2017
Ίδρυμα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Εξεταστική επιτροπή
Θηλυκός Δημήτριος
Κολιόπουλος Σταύρος
Ράπτης Ευάγγελος
Δρακόπουλος Μιχαήλ
Κυρούσης Ελευθέριος
Πιτσούλης Λεωνίδας
Μούρτος Ιωάννης
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΜαθηματικά
Λέξεις-κλειδιά
Παρεμποδίσεις; Διατάξεις γραφημάτων; Θεωρία γραφημάτων; Παραμετρική πολυπλοκότητα; Ανίχνευση σε γραφήματα; Ελάσσονα γραφήματος; Εμβυθίσεις γραφήματος; Συνθλίψεις γραφήματος; Πλάτος τομών; Πυρηνοποίηση
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
vii, 320 σ., σχημ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)