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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00045215" target="_blank" >RIV/00216224:14330/10:00045215 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původní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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

<a href="/cs/project/GC201%2F09%2FJ021" target="_blank" >GC201/09/J021: Strukturální teorie grafů a parametrizovaná složitost</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

SOFSEM 2011: Theory and Practice of Computer Science

ISBN

978-3-642-18380-5

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

—

Název nakladatele

Springer-Verlag

Místo vydání

Nový Smokovec, Slovensko

Místo konání akce

Nový Smokovec, Slovensko

Datum konání akce

1. 1. 2011

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000000