Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

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.

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 × 11

Rights

dc:rights
Statement dc:rights
  • BY
Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/45972

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Chatzidimitriou, Dimitrios; Χατζηδημητρίου, Δημήτριος. Παραμετρικοί - προσεγγιστικοί αλγόριθμοι και ιδιότητες Erdős-Pósa σε γραφήματα. National and Kapodistrian University of Athens, 2019. http://hdl.handle.net/10442/hedi/45972