5 citations · 5 across the 3 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2011
Computing hypergraph width measures exactly
Lukas Moll, Siamak Tazari, Marc Thurley
Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponenti…
cs.CC2011
Counting Homomorphisms and Partition Functions
Martin Grohe, Marc Thurley
Homomorphisms between relational structures are not only fundamental mathematical objects, but are also of great importance in an applied computational context. Indeed, constraint…
cs.CC2008★ 5 cited
A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum +1
Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the nu…