13 citations · 46 across the 31 of their papers we have counts for
3 papers · 2 filters
Complexity and Approximability of Parameterized MAX-CSPs
Holger Dell, Eun Jung Kim, Michael Lampis +2
We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constr…
Sub-exponential Approximation Schemes for CSPs: from Dense to Almost Sparse
Dimitris Fotakis, Michael Lampis, Vangelis Th. Paschos
It has long been known, since the classical work of (Arora, Karger, Karpinski, JCSS~99), that \MC\ admits a PTAS on dense graphs, and more generally, \kCSP\ admits a PTAS on "dense…
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a…