| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00066750 |
| Název v původním jazyce | Parameterized Algorithms for Modular-Width |
| 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 | 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í | 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 | 80,0 % | 36,945 | 18,513 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 3 |
| Počet domácích tvůrců | 2 |
| Tvůrce | Gajarský Jakub (státní příslušnost: SK - Slovenská republika; A - domácí tvůrce; vedidk: 9663207) |
| Tvůrce | Lampis Michael (státní příslušnost: GR - Řecká republika) |
| Tvůrce | Ordyniak Sebastian (státní příslušnost: DE - Spolková republika Německo; A - domácí tvůrce) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | It is known that a number of natural graph problems which are FPT parameterized by treewidth become W-hard when parameterized by clique-width. It is therefore desirable to find a different structural graph parameter which is as general as possible, covers dense graphs but does not incur such a heavy algorithmic penalty. The main contribution of this paper is to consider a parameter called modular-width, defined using the well-known notion of modular decompositions. Using a combination of ILP and dynamic programming we manage to design FPT algorithms for Coloring and Partitioning into paths (and hence Hamiltonian path and Hamiltonian cycle), which are W-hard for both clique-width and its recently introduced restriction, shrub-depth. We thus argue that modular-width occupies a sweet spot as a graph parameter, generalizing several simpler notions on dense graphs but still evading the “price of generality” paid by clique-width. |
| Klíčová slova | parameterized complexity; modular width; shrub depth; chromatic number; hamiltonian path |
| Rozsah stran | 163-176 |
| Název sborníku | Parameterized and Exact Computation |
| Forma vydání | P - Tištěná verze „print“ |
| ISSN | 0302-9743 |
| Počet stran výsledku | 14 |
| ISBN | 9783319038971 |
| Název nakladatele | Springer International Publishing |
| Místo vydání | Berlin Heidelberg |
| Místo konání akce | Sophia Antipolis, 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-319-03898-8_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:00066750!RIV14-GA0-14330___ |
| Kontrolní kód | [96E8852E82AC] |
| 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/13:00066750 v dodávce dat RIV14-MSM-14330___/01:1 |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | EE2.3.30.0009 - Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci (2012-2015, MSM/EE) |
| 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) |