37 citations · 102 across the 14 of their papers we have counts for
4 papers · 1 filter
Tree-depth and Vertex-minors
Petr Hliněný, O-joung Kwon, Jan Obdržálek +1
In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already befor…
FO Model Checking of Interval Graphs
Robert Ganian, Petr Hlineny, Daniel Kral +3
We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that…
Better algorithms for satisfiability problems for formulas of bounded rank-width
Robert Ganian, Petr Hliněný, Jan Obdržálek
We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previo…
Are there any good digraph width measures?
Robert Ganian, Petr Hliněný, Joachim Kneis +4
Several different measures for digraph width have appeared in the last few years. However, none of them shares all the "nice" properties of treewidth: First, being \emph{algorithmi…