| Identifikační kód | RIV/00216224:14330/11:00065885 |
|---|
| Název v anglickém jazyce | New Results on the Complexity of the Max- and Min-Rep Problems |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | B - Fyzika a matematika |
|---|
| Obor | BD - Teorie informace |
|---|
| Rok uplatnění | 2011 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 1 |
|---|
| Počet domácích tvůrců | 1 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Robert Ganian (státní příslušnost: US - Spojené státy americké, domácí tvůrce: A, vedidk: 6376290) |
|---|
| Popis výsledku v anglickém jazyce | 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 aredesperately 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. |
|---|
| Klíčová slova oddělená středníkem | Max-Rep; Min-Rep; Parameterized Complexity |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1007/978-3-642-11266-9_36 |
|---|