37 citations · 102 across the 14 of their papers we have counts for
3 papers · 1 filter
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…
Qualitative Reachability in Stochastic BPA Games
Tomáš Brázdil, Václav Brožek, Antonín Kučera +1
We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is…