12 citations · 34 across the 17 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.LO2015
Efficient computation of generalized Ising polynomials on graphs with fixed clique-width
Tomer Kotek, Johann A. Makowsky
Graph polynomials which are definable in Monadic Second Order Logic (MSOL) on the vocabulary of graphs are Fixed-Parameter Tractable (FPT) with respect to clique-width. In contrast…
cs.LO2015
Monadic second order finite satisfiability and unbounded tree-width
Tomer Kotek, Helmut Veith, Florian Zuleger
The finite satisfiability problem of monadic second order logic is decidable only on classes of structures of bounded tree-width by the classic result of Seese (1991). We prove the…