| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/13:00065951 |
| Název v původním jazyce | Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width |
| Druh | J - Článek v odborném periodiku |
| 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í | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Článek v impaktovaném časopise evidovaném ve Web of Science |
| Bodové ohodnocení | 27,889 |
| Faktor korekce | 86,1 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 24,018 |
| 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 % | 27,889 | 24,018 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 3 |
| Počet domácích tvůrců | 3 |
| Tvůrce | Ganian Robert (státní příslušnost: US - Spojené státy americké; A - domácí tvůrce; vedidk: 6376290) |
| Tvůrce | Hliněný Petr (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 7595646) |
| Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; vedidk: 3294099) |
| Údaje blíže specifikující výsledek |
| Popis v původním jazyce | In this paper we develop new algorithmic machinery for solving hard problems on graphs of bounded rank-width and on digraphs of bounded bi-rank-width in polynomial (XP, to be precise) time. These include, particularly, graph coloring and chromatic polynomial problems, the Hamiltonian path and c-min-leaf outbranching, the directed cut, and more generally MSOL-partitioning problems on digraphs. Our focus on a formally clean and unified approach for the considered algorithmic problems is in contrast with many previous published XP algorithms running on graphs of bounded clique-width, which mostly used ad hoc techniques and ideas. The new contributions include faster algorithms for computing the chromatic number and the chromatic polynomial on graphs of bounded rank-width, and new algorithms for solving the defective coloring, the min-leaf outbranching, and the directed cut problems. |
| Klíčová slova | rank-width; XP algorithm; coloring |
| Kód UT ISI | 000314075000012 |
| Název periodka | European Journal of Combinatorics |
| Rozsah stran | 680-701 |
| ISSN | 0195-6698 |
| Svazek periodika | 34 |
| Číslo periodika v rámci uvedeného svazku | 3 |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 22 |
| DOI výsledku | 10.1016/j.ejc.2012.07.024 |
| Ú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:00065951!RIV14-GA0-14330___ |
| Kontrolní kód | [8E4EE527D35D] |
| 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) |
| Projekt | GC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009-2010, GA0/GC) |