This HTML5 document contains 50 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n12http://localhost/temp/predkladatel/
n14http://linked.opendata.cz/resource/domain/vavai/projekt/
n10http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n7http://linked.opendata.cz/ontology/domain/vavai/
n11http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F14%3A00073690%21RIV15-GA0-14330___/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
n19http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n5http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n16http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n8http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F14%3A00073690%21RIV15-GA0-14330___
rdf:type
n7:Vysledek skos:Concept
dcterms:description
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. 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.
dcterms:title
Digraph width measures in parameterized algorithmics Digraph width measures in parameterized algorithmics
skos:prefLabel
Digraph width measures in parameterized algorithmics Digraph width measures in parameterized algorithmics
skos:notation
RIV/00216224:14330/14:00073690!RIV15-GA0-14330___
n4:aktivita
n15:P
n4:aktivity
P(GBP202/12/G061), P(GC201/09/J021)
n4:cisloPeriodika
1
n4:dodaniDat
n8:2015
n4:domaciTvurceVysledku
n10:7595646 n10:3294099 n10:6376290
n4:druhVysledku
n17:J
n4:duvernostUdaju
n9:S
n4:entitaPredkladatele
n11:predkladatel
n4:idSjednocenehoVysledku
11556
n4:idVysledku
RIV/00216224:14330/14:00073690
n4:jazykVysledku
n16:eng
n4:klicovaSlova
Digraph; Parameterized complexity; Tree-width; DAG-width; DAG-depth; Clique-width
n4:klicoveSlovo
n5:Clique-width n5:DAG-width n5:Tree-width n5:Digraph n5:Parameterized%20complexity n5:DAG-depth
n4:kodStatuVydavatele
NL - Nizozemsko
n4:kontrolniKodProRIV
[783BEADA1B6A]
n4:nazevZdroje
Discrete Applied Mathematics
n4:obor
n18:IN
n4:pocetDomacichTvurcuVysledku
3
n4:pocetTvurcuVysledku
6
n4:projekt
n14:GBP202%2F12%2FG061 n14:GC201%2F09%2FJ021
n4:rokUplatneniVysledku
n8:2014
n4:svazekPeriodika
168
n4:tvurceVysledku
Rossmanith, Peter Kneis, Joachim Obdržálek, Jan Ganian, Robert Hliněný, Petr Langer, Alexander
n4:wos
000334485900011
s:issn
0166-218X
s:numberOfPages
20
n19:doi
10.1016/j.dam.2013.10.038
n12:organizacniJednotka
14330