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

Περίληψη

Η σύγχρονη Θεωρία Γραφημάτων έχει επηρεαστεί σε μεγάλο βαθμό από την δουλειά των 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.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

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