Digraph width measures in parameterized algorithmics (2014)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/14:00073690 |
|---|---|
| Název v anglickém jazyce | Digraph width measures in parameterized algorithmics |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2014 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 6 |
| Počet domácích tvůrců | 3 |
| Výčet všech uvedených jednotlivých tvůrců | Robert Ganian (státní příslušnost: US - Spojené státy americké, domácí tvůrce: A, vedidk: 6376290) Petr Hliněný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 7595646) Joachim Kneis (státní příslušnost: DE - Spolková republika Německo) Alexander Langer (státní příslušnost: DE - Spolková republika Německo) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) Peter Rossmanith (státní příslušnost: DE - Spolková republika Německo) |
| Popis výsledku v anglickém jazyce | In contrast to undirected width measures such as tree-width, which have provided many important algorithmic applications, analogous measures for digraphs such as directed tree-width or DAG-width do not seem so successful. Several recent papers have givensome evidence on the negative side. We confirm and consolidate this overall picture by thoroughly and exhaustively studying the complexity of a range of directed problems with respect to various parameters, and by showing that they often remain NP-hardeven on graph classes that are restricted very beyond having small DAG-width. On the positive side, it turns out that clique-width (of digraphs) performs much better on virtually all considered problems, from the parameterized complexity point of view. |
| Klíčová slova oddělená středníkem | Digraph; Parameterized complexity; Tree-width; DAG-width; DAG-depth; Clique-width |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1016/j.dam.2013.10.038 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Discrete Applied Mathematics |
|---|---|
| ISSN | 0166-218X |
| Svazek periodika | 168 |
| Číslo periodika v rámci uvedeného svazku | 1 |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 20 |
| Strana od-do | 88-107 |
| Kód UT WoS článku podle Web of Science | 000334485900011 |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2015 |
| Specifikace | RIV/00216224:14330/14:00073690!RIV15-GA0-14330___ |
| Datum poslední aktualizace výsledku | 12.05.2015 |
| Kontrolní číslo | 152517434 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GB | GBP202/12/G061 - Centrum excelence - Institut teoretické informatiky (CE-ITI) (2012 - 2018) |
|---|---|
| Projekt podporovaný GA ČR v programu GC | GC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009 - 2010) |