J 2014

Digraph width measures in parameterized algorithmics

GANIAN, Robert, Petr HLINĚNÝ, Joachim KNEIS, Alexander LANGER, Jan OBDRŽÁLEK et. al.

Základní údaje

Originální název

Digraph width measures in parameterized algorithmics

Autoři

GANIAN, Robert (840 Spojené státy, domácí), Petr HLINĚNÝ (203 Česká republika, domácí), Joachim KNEIS (276 Německo), Alexander LANGER (276 Německo), Jan OBDRŽÁLEK (203 Česká republika, garant, domácí) a Peter ROSSMANITH (276 Německo)

Vydání

Discrete Applied Mathematics, Elsevier B.V. 2014, 0166-218X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.802

Kód RIV

RIV/00216224:14330/14:00073690

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000334485900011

Klíčová slova anglicky

Digraph;Parameterized complexity;Tree-width;DAG-width;DAG-depth;Clique-width

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 1. 4. 2015 22:53, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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 given some 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-hard even 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.

Návaznosti

GBP202/12/G061, projekt VaV
Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)
Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky
GC201/09/J021, projekt VaV
Název: Strukturální teorie grafů a parametrizovaná složitost
Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost