6 citations · 23 across the 15 of their papers we have counts for
Showing 2007 · math.COShow all
2 papers · 2 filters
math.CO2007
Forbidden lists (NP and CSP for combinatorialists)
Gabor Kun, Jaroslav Nesetril
We present a definition of the class NP in combinatorial context as the set of languages of structures defined by finitely many forbidden lifted substructures. We apply this to spe…
math.CO2007★ 6 cited
Constraints, MMSNP and expander relational structures
Gabor Kun
We give a poly-time construction for a combinatorial classic known as Sparse Incomparability Lemma, studied by Erdos, Lovasz, Nesetril, Rodl and others: We show that every Constrai…