1 citations · 1 across the 5 of their papers we have counts for
5 papers
Pebble-Intervals Automata and FO2 with Two Orders (Extended Version)
Nadia Labai, Tomer Kotek, Magdalena Ortiz +1
We introduce a novel automata model, called pebble-intervals automata (PIA), and study its power and closure properties. PIAs are tailored for a decidable fragment of FO that is im…
The exact complexity of the Tutte polynomial
Tomer Kotek, Johann A. Makowsky
This is a survey on the exact complexity of computing the Tutte polynomial. It is the longer 2017 version of Chapter 25 of the CRC Handbook on the Tutte polynomial and related topi…
On sequences of polynomials arising from graph invariants
T. Kotek, J. A. Makowsky, E. V. Ravve
Graph polynomials are deemed useful if they give rise to algebraic characterizations of various graph properties, and their evaluations encode many other graph invariants. Algebrai…
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…
Subset-Sum Representations of Domination Polynomials
Tomer Kotek, James Preen, Peter Tittmann
The domination polynomial D(G,x) is the ordinary generating function for the dominating sets of an undirected graph G=(V,E) with respect to their cardinality. We consider in this p…