29 citations · 212 across the 50 of their papers we have counts for
7 papers · 1 filter
FPT Algorithms for Diverse Collections of Hitting Sets
Julien Baste, Lars Jaffke, Tomáš Masařík +2
In this work, we study the -Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of solutions of size at most each, which has…
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
Packing Directed Cycles Quarter- and Half-Integrally
Tomáš Masařík, Irene Muzi, Marcin Pilipczuk +2
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of vertex-disjoint cycles contains a feedback vertex set (a set of vertices hi…
Flexibility of planar graphs without 4-cycles
Tomáš Masařík
Proper graph coloring assigns different colors to adjacent vertices of the graph. Usually, the number of colors is fixed or as small as possible. Consider applications (e.g. varian…
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory
Julien Baste, Michael R. Fellows, Lars Jaffke +4
When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instanc…
Flexibility of planar graphs of girth at least six
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G has girth at least six and all lists have size at…
Flexibility of triangle-free planar graphs
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek +1
Let G be a planar graph with a list assignment L. Suppose a preferred color is given for some of the vertices. We prove that if G is triangle-free and all lists have size at least…