16 citations · 94 across the 30 of their papers we have counts for
7 papers · 1 filter
Clique-Width of Point Configurations
Onur Çağırıcı, Petr Hliněný, Filip Pokrývka +1
While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose…
A New Perspective on FO Model Checking of Dense Graph Classes
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +2
We study the first-order (FO) model checking problem of dense graphs, namely those which have FO interpretations in (or are FO transductions of) some sparse graph classes. We give…
FO model checking of geometric graphs
Petr Hliněný, Filip Pokrývka, Bodhayan Roy
Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures - culminating in the FPT algorithm by…
Shrub-depth: Capturing Height of Dense Graphs
Robert Ganian, Petr Hliněný, Jaroslav Nešetřil +2
The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogousl…
FO Model Checking on Posets of Bounded Width
Jakub Gajarský, Petr Hliněný, Daniel Lokshtanov +4
Over the past two decades the main focus of research into first-order (FO) model checking algorithms have been sparse relational structures-culminating in the FPT-algorithm by Groh…
Faster Existential FO Model Checking on Posets
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +1
We prove that the model checking problem for the existential fragment of first-order (FO) logic on partially ordered sets is fixed-parameter tractable (FPT) with respect to the for…