New Results on the Complexity of the Max- and Min-Rep Problems

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

GANIAN Robert

Rok publikování 2011
Druh Článek ve sborníku
Konference SOFSEM 2011: Theory and Practice of Computer Science
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://www.sofsem.sk
Doi http://dx.doi.org/10.1007/978-3-642-11266-9_36
Obor Teorie informace
Klíčová slova Max-Rep; Min-Rep; Parameterized Complexity
Popis This paper deals with the Max-Rep and Min-Rep problems, both of which are related to the famous Label Cover problem. These are of notable theoretical interest, since they are often used to prove hardness results for other problems. In many cases new complexity results for these problems may be preserved by the reductions, and so new results for Max-Rep and Min-Rep could be applicable to a wide range of other problems as well. Both Max- and Min-Rep are strongly inapproximable. Thus, other approaches are desperately needed to tackle these hard problems. In our paper we use the very successful parameterized complexity paradigm and obtain new complexity results for various parameterizations of the problems.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.