Dimitrios M. Thilikos

most citedExplicit linear kernels for packing problems

1 citations · 1 across the 3 of their papers we have counts for

collaborators

6 papers

math.CO2024

Obstructions to Erdős-Pósa Dualities for Minors

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1

Let $G$ and $H$ be minor-closed graph classes. The pair $(H, G)$ is an Erdős-Pósa pair (EP-pair) if there is a function $f$ where, for every $k$ and ever…

cs.LO2024

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Given a graph $G$ and a vertex set $X$ , the annotated treewidth tw $(G, X)$ of $X$ in $G$ is the maximum treewidth of an $X$ -rooted minor of $G$ , i.e., a minor $H$ where the model of…

math.CO2024

Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1

In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for…

math.CO2022

Contraction Bidimensionality of Geometric Intersection Graphs

Julien Baste, Dimitrios M. Thilikos

Given a graph $G$ , we define $bcg (G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $Γ_{k}$ . A graph class $G$ has the SQG${\bf…

math.CO2022

Combing a Linkage in an Annulus

Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

A linkage in a graph $G$ of size $k$ is a subgraph $L$ of $G$ whose connected components are $k$ paths. The pattern of a linkage of size $k$ is the set of $k$ pairs formed by the e…

cs.DS2016★ 1 cited

Explicit linear kernels for packing problems

Valentin Garnero, Christophe Paul, Ignasi Sau +1

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence…