11 papers
Fair Vertex Problems Parameterized by Cluster Vertex Deletion
Tomáš MasaÅÃk, JÄdrzej Olkowski, Anna Zych-Pawlewicz
In this paper we study fair variants of MSO definable problems parameterized by cluster vertex deletion number, i.e., the smallest number of vertices required to be removed fro…
Finding Diverse Solutions Parameterized by Cliquewidth
Karolina Drabik, Tomáš MasaÅÃk
Finding a few solutions for a given problem that are diverse, as opposed to finding a single best solution to solve the problem, has recently become a notable topic in theoretical…
Separator Theorem for Minor-Free Graphs in Linear Time
Ãdouard Bonnet, Tuukka Korhonen, Hung Le +2
The planar separator theorem by Lipton and Tarjan [FOCS '77, SIAM Journal on Applied Mathematics '79] states that any planar graph with vertices has a balanced separator of siz…
Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
Peter Gartland, Daniel Lokshtanov, Tomáš MasaÅÃk +3
We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on -free graphs (graphs excluding a fixed graph as an induced subgraph)…
Minimizing an Uncrossed Collection of Drawings
Petr HlinÄný, Tomáš MasaÅÃk
In this paper, we introduce the following new concept in graph drawing. Our task is to find a small collection of drawings such that they all together satisfy some property that is…
Constricting the Computational Complexity Gap of the -Coloring Problem in -free Graphs
Justyna Jaworska, BartÅomiej Kielak, Tomáš MasaÅÃk +1
The -Coloring problem on hereditary graph classes has been a deeply researched problem over the last decade. A hereditary graph class is characterized by a (possibly infinite) l…