16 citations · 94 across the 30 of their papers we have counts for
5 papers · 1 filter
Lower Bounds on the Complexity of MSO1 Model-Checking
Robert Ganian, Petr Hliněný, Alexander Langer +3
One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quant…
Generalized Maneuvers in Route Planning
Petr Hlineny, Ondrej Moris
We study an important practical aspect of the route planning problem in real-world road networks -- maneuvers. Informally, maneuvers represent various irregularities of the road ne…
How Not to Characterize Planar-emulable Graphs
Markus Chimani, Martin Derka, Petr Hliněný +1
We investigate the question of which graphs have planar emulators (a locally-surjective homomorphism from some finite planar graph) -- a problem raised already in Fellows' thesis (…
A Tighter Insertion-based Approximation of the Crossing Number
Markus Chimani, Petr Hlineny
Let G be a planar graph and F a set of additional edges not yet in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge c…
Multi-Stage Improved Route Planning Approach: theoretical foundations
Petr Hlineny, Ondrej Moris
A new approach to the static route planning problem, based on a multi-staging concept and a \emph{scope} notion, is presented. The main goal (besides implied efficiency of planning…