National and Kapodistrian University of Athens
Παραμετρικοί - προσεγγιστικοί αλγόριθμοι και ιδιότητες Erdős-Pósa σε γραφήματα
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- National and Kapodistrian University of Athens
- Year dc:date
- 2019
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Chatzidimitriou, Dimitrios
- Χατζηδημητρίου, Δημήτριος
Subjects
dc:subject × 11Rights
dc:rights- Statement dc:rights
-
- BY
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/45972