1. Home page
  2. Search

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

This item is provided by the institution :
National Documentation Centre (EKT)   

Repository :
National Archive of PhD Theses  | ΕΚΤ NA.Ph.D.   

see the original item page
in the repository's web site and access all digital files if the item*



Parameterized - approximation algorithms and Erdős-Pósa properties on graphs
Παραμετρικοί - προσεγγιστικοί αλγόριθμοι και ιδιότητες Erdős-Pósa σε γραφήματα
Chatzidimitriou, Dimitrios
Χατζηδημητρίου, Δημήτριος
PhD Thesis
2019
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.
Η διατριβή αυτή επικεντρώνεται στη μελέτη παραμετρικών προσεγγιστικών αλγορίθμων που σχετίζονται με γραφήματα κολοκύθες. Χρησιμοποιώντας μία γενικευμένη προσέγγιση (που μπορεί να επεκταθεί και σε πιο γενικές κλάσεις γραφημάτων) σχεδιάζουμε αλγορίθμους που ανιχνεύουν μοντέλα κολοκυθών και που χτυπούν μοντέλα κολοκυθών σε μεγάλα γραφήματα. Στηριζόμενοι σε αυτούς τους αλγόριθμους αποδεικνύουμε ιδιότητες τύπου Erdős-Pósa ως προς κορυφές και ακμές για τις κλάσεις των κολοκυθών και των διπλών κολοκυθών· για την πρώτη βελτιώνουμε υπάρχοντα αποτελέσματα ενώ για τη δεύτερη παρέχουμε τα πρώτα του είδους τους. Στην πορεία προς τούτο, γενικεύουμε προηγούμενα αποτέλεσματα που παρέχουν συνθήκες οι οποίες εξαναγκάζουν την ύπαρξη μιας ελάσσονος κλίκας εκθετικού μεγέθους μέσα σε ένα μεγαλύτερο γράφημα-φορέα.
Μαθηματικά
Φυσικές Επιστήμες
Erdős-Pósa
Approximation algorithms
Μαθηματικά
Προσεγγιστικοί αλγόριθμοι
Parameterized algorithms
Mathematics
Pumpkin graphs
Natural Sciences
Παραμετρικοί αλγόριθμοι
Γραφήματα κολοκύθας
Φυσικές Επιστήμες
Greek
National and Kapodistrian University of Athens
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ)
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών (ΕΚΠΑ). Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών. Τομέας Μαθηματικής Ανάλυσης
BY
National Documentation Centre (EKT)
National Archive of PhD Theses
Συλλογή ΕΑΔΔ



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)