| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/11:00065885 |
| Název v původní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 | BD - Teorie informace |
| Rok uplatnění | 2011 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 2 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | D - Článek ve sborníku |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Článek ve sborníku evidovaném v databázi Scopus bodovaný podle SJR zdroje typu Book Series nebo Conference Proceedings |
| Bodové ohodnocení | 53,461 |
| Faktor korekce | 100,9 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 53,957 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 100,0 % | 53,461 | 53,957 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 1 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Ganian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; vedidk: 6376290) |
| Údaje blíže specifikující výsledek |
| Popis 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 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. |
| Klíčová slova | Max-Rep; Min-Rep; Parameterized Complexity |
| Kód UT ISI | 000296264200020 |
| Název sborníku | SOFSEM 2011: Theory and Practice of Computer Science |
| Rozsah stran | 238-247 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| Počet stran výsledku | 10 |
| ISBN | 9783642050053 |
| Název nakladatele | Springer-Verlag |
| Místo vydání | Nový Smokovec, Slovensko |
| Místo konání akce | Nový Smokovec, Slovensko |
| Rok konání akce | 2011 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.1007/978-3-642-11266-9_36 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2014 |
| Systémové označení dodávky dat | RIV14-GA0-14330___/01:1 |
| Specifikace | RIV/00216224:14330/11:00065885!RIV14-GA0-14330___ |
| Kontrolní kód | [BC7709831F64] |
| Další výskyty tohoto výsledku od stejného předkladatele |
| Dodáno MŠMT v roce 2014 | Záznam s identifikačním kódem RIV/00216224:14330/11:00065885 v dodávce dat RIV14-MSM-14330___/01:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009-2010, GA0/GC) |
| Výzkumný záměr | MSM0021622419 - Vysoce paralelní a distribuované výpočetní systémy (2005-2011, MSM) |
| S - Specifický výzkum na vysokých školách |