| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00066545 |
| Název v původním jazyce | Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes |
| Druh | D - Článek ve sborníku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2013 |
| 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 | 1 |
| Ú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í | 46,181 |
| Faktor korekce | 50,1 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 23,141 |
| 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 | 66,7 % | 30,787 | 15,427 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 2 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 3294099) |
| Tvůrce | Ganian Robert (státní příslušnost: US - Spojené státy americké; vedidk: 6376290) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | We combine integer linear programming and recent advances in Monadic Second-Order model checking to obtain two new algorithmic meta-theorems for graphs of bounded vertex-cover. The first one shows that the model checking problem for cardMSO1, an extension of the well-known Monadic Second-Order logic by the addition of cardinality constraints, can be solved in FPT time parameterized by vertex cover. The second meta-theorem shows that the MSO partitioning problems introduced by Rao can also be solved in FPT time with the same parameter. The significance of our contribution stems from the fact that these formalisms can describe problems which are W[1]-hard and even NP-hard on graphs of bounded tree-width. Additionally, our algorithms have only elementary dependence on the parameter and formula. We also show that both results are easily extended from vertex cover to neighborhood diversity. |
| Klíčová slova | MSO; model checking; vertex cover; meta-theorems; parameterized complexity |
| Název sborníku | Combinatorial Algorithms 24th International Workshop, IWOCA 2013 |
| Rozsah stran | 164-177 |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| ISBN | 9783642452772 |
| Počet stran výsledku | 14 |
| Název nakladatele | Springer-Verlag |
| Místo vydání | Berlin Heidelberg |
| Místo konání akce | Rouen, France |
| Rok konání akce | 2013 |
| Typ akce podle státní příslušnoti účastníků | WRD - Světová |
| DOI výsledku | 10.1007/978-3-642-45278-9_15 |
| Ú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/13:00066545!RIV14-GA0-14330___ |
| Kontrolní kód | [101D95EA52D4] |
| Jiný výskyt tohoto výsledku se v RIV nenachází |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GAP202/11/0196 - Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů (2011-2013, GA0/GA) |