Tomáš Masařík

activity

20152026

most citedDiversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory

29 citations · 212 across the 50 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.CC2017★ 10 cited

Notes on complexity of packing coloring

Minki Kim, Bernard Lidický, Tomáš Masařík +1

A packing $k$ -coloring for some integer $k$ of a graph $G = (V, E)$ is a mapping $φ : V \to {1, \dots, k}$ such that any two vertices $u, v$ of color $φ (u) = φ (v)$ are in distance at least…

cs.DS2017★ 9 cited

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices

Pavel Dvořák, Andreas Emil Feldmann, Dušan Knop +3

We study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensive…

cs.CC2017★ 21 cited

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

Dušan Knop, Martin Koutecký, Tomáš Masařík +1

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidt…