16 citations · 94 across the 30 of their papers we have counts for
7 papers · 1 filter
Crossing Number is Hard for Kernelization
Petr Hliněný, Marek Derňár
The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult,…
Parameterized Extension Complexity of Independent Set and Related Problems
Jakub Gajarský, Petr Hliněný, Hans Raj Tiwary
Let be a graph on vertices and be the convex hull of characteristic vectors of its independent sets of size at most . We study extension complexity…
Inserting Multiple Edges into a Planar Graph
Markus Chimani, Petr Hliněný
Let be a connected planar (but not yet embedded) graph and a set of additional edges not yet in . The {multiple edge insertion} problem (MEI) asks for a drawing of …
On Hardness of the Joint Crossing Number
Petr Hliněný, Gelasio Salazar
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minim…
Strategy Synthesis in Adversarial Patrolling Games
Tomáš Brázdil, Petr Hliněný, Antonín Kučera +2
Patrolling is one of the central problems in operational security. Formally, a patrolling problem is specified by a set of nodes (admissible defender's positions), a set $T \su…
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…