Παραμετρικοί - προσεγγιστικοί αλγόριθμοι και ιδιότητες 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.
![]() | |
![]() | Κατεβάστε τη διατριβή σε μορφή PDF (569.83 kB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
|
Στατιστικά χρήσης
![](/eadd/image/spinner.gif)
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
![](/eadd/image/spinner.gif)
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
![](/eadd/image/spinner.gif)
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
![](/eadd/image/spinner.gif)
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.