Παραμετρικοί - προσεγγιστικοί αλγόριθμοι και ιδιότητες Erdős-Pósa σε γραφήματα

Περίληψη

Η διατριβή αυτή επικεντρώνεται στη μελέτη παραμετρικών προσεγγιστικών αλγορίθμων που σχετίζονται με γραφήματα κολοκύθες. Χρησιμοποιώντας μία γενικευμένη προσέγγιση (που μπορεί να επεκταθεί και σε πιο γενικές κλάσεις γραφημάτων) σχεδιάζουμε αλγορίθμους που ανιχνεύουν μοντέλα κολοκυθών και που χτυπούν μοντέλα κολοκυθών σε μεγάλα γραφήματα. Στηριζόμενοι σε αυτούς τους αλγόριθμους αποδεικνύουμε ιδιότητες τύπου Erdős-Pósa ως προς κορυφές και ακμές για τις κλάσεις των κολοκυθών και των διπλών κολοκυθών· για την πρώτη βελτιώνουμε υπάρχοντα αποτελέσματα ενώ για τη δεύτερη παρέχουμε τα πρώτα του είδους τους. Στην πορεία προς τούτο, γενικεύουμε προηγούμενα αποτέλεσματα που παρέχουν συνθήκες οι οποίες εξαναγκάζουν την ύπαρξη μιας ελάσσονος κλίκας εκθετικού μεγέθους μέσα σε ένα μεγαλύτερο γράφημα-φορέα.

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

This thesis is centred around the study of parameterized approximation algorithms related to pumpkin graphs. Using a generalised approach (which could be expanded to other graph classes) we design algorithms that find pumpkin models and hit pumpkin models in large graphs. Based on these algorithms we prove Erdős-Pósa-like results, both for vertices and edges, for the classes of pumpkins and double pumpkins; for the former we improve previous results and for the latter we provide the first such results. As a necessary step in our process, but of independent value, we generalise previous results that provide conditions which force the existence of a clique of exponential size as a minor inside a larger host graph.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

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

Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/45972
ND
45972
Εναλλακτικός τίτλος
Parameterized - approximation algorithms and Erdős-Pósa properties on graphs
Συγγραφέας
Χατζηδημητρίου, Δημήτριος Αθανάσιος
Ημερομηνία
2019
Ίδρυμα
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών. Τομέας Μαθηματικής Ανάλυσης
Εξεταστική επιτροπή
Θηλυκός Δημήτριος
Κυρούσης Ελευθέριος
Κολλιόπουλος Σταύρος
Γεωργιάδης Λουκάς
Γιαννοπούλου Αρχοντία
Δρακόπουλος Μιχαήλ
Παπαδόπουλος Ιωάννης
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Μαθηματικά
Λέξεις-κλειδιά
Παραμετρικοί αλγόριθμοι; Προσεγγιστικοί αλγόριθμοι; Γραφήματα κολοκύθας; Παραμετρικοί αλγόριθμοι
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά
Άλλα στοιχεία
91 σ., σχημ., γραφ.
Ειδικοί όροι χρήσης/διάθεσης
Το έργο παρέχεται υπό τους όρους της δημόσιας άδειας του νομικού προσώπου Creative Commons Corporation:Creative Commons Αναφορά Δημιουργού 3.0 Ελλάδα