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

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

Namespace Prefixes

PrefixIRI
n18http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n8http://localhost/temp/predkladatel/
n11http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216224%3A14330%2F10%3A00065874%21RIV14-MSM-14330___/
n7http://purl.org/net/nknouf/ns/bibtex#
n13http://linked.opendata.cz/resource/domain/vavai/projekt/
n10http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n16http://linked.opendata.cz/ontology/domain/vavai/
n5https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
n17http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n20http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n22http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n6http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n21http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216224%3A14330%2F10%3A00065874%21RIV14-MSM-14330___
rdf:type
n16:Vysledek skos:Concept
dcterms:description
Oriented colouring is a quite intuitive generalization of undirected colouring, yet the problem remains NP-hard even on digraph classes with bounded usual directed width measures. In light of this fact, one might ask whether new width measures are required for efficient dealing with this problem or whether further restriction of traditional directed width measures such as DAG-width would suffice. The K-width and DAG-depth measures (introduced by [Ganian et al, IWPEC09]) are ideal candidates for tackling this question: They are both closely tied to the cops-and-robber games which inspire and characterize the most renowned directed width measures, while at the same time being much more restrictive. In this paper, we look at the oriented colouring problem on digraphs of bounded K-width and of bounded DAG-depth. Oriented colouring is a quite intuitive generalization of undirected colouring, yet the problem remains NP-hard even on digraph classes with bounded usual directed width measures. In light of this fact, one might ask whether new width measures are required for efficient dealing with this problem or whether further restriction of traditional directed width measures such as DAG-width would suffice. The K-width and DAG-depth measures (introduced by [Ganian et al, IWPEC09]) are ideal candidates for tackling this question: They are both closely tied to the cops-and-robber games which inspire and characterize the most renowned directed width measures, while at the same time being much more restrictive. In this paper, we look at the oriented colouring problem on digraphs of bounded K-width and of bounded DAG-depth.
dcterms:title
New results on the complexity of oriented colouring on restricted digraph classes New results on the complexity of oriented colouring on restricted digraph classes
skos:prefLabel
New results on the complexity of oriented colouring on restricted digraph classes New results on the complexity of oriented colouring on restricted digraph classes
skos:notation
RIV/00216224:14330/10:00065874!RIV14-MSM-14330___
n4:aktivita
n6:S n6:P
n4:aktivity
P(GA201/08/0308), P(GC201/09/J021), S
n4:dodaniDat
n21:2014
n4:domaciTvurceVysledku
n10:7595646 n10:6376290
n4:druhVysledku
n14:D
n4:duvernostUdaju
n22:S
n4:entitaPredkladatele
n11:predkladatel
n4:idSjednocenehoVysledku
274759
n4:idVysledku
RIV/00216224:14330/10:00065874
n4:jazykVysledku
n15:eng
n4:klicovaSlova
Directed graph; complexity; oriented colouring; DAG-depth
n4:klicoveSlovo
n20:DAG-depth n20:complexity n20:oriented%20colouring n20:Directed%20graph
n4:kontrolniKodProRIV
[7B63064EB386]
n4:mistoKonaniAkce
Špindlerův mlýn
n4:mistoVydani
Berlin
n4:nazevZdroje
SOFSEM 2010, Lecture Notes in Computer Science 5901
n4:obor
n9:IN
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
2
n4:projekt
n13:GC201%2F09%2FJ021 n13:GA201%2F08%2F0308
n4:rokUplatneniVysledku
n21:2010
n4:tvurceVysledku
Ganian, Robert Hliněný, Petr
n4:typAkce
n18:EUR
n4:wos
000280086900036
n4:zahajeniAkce
2010-01-01+01:00
s:issn
0302-9743
s:numberOfPages
12
n17:doi
10.1007/978-3-642-11266-9_36
n7:hasPublisher
Springer-Verlag
n5:isbn
9783642112652
n8:organizacniJednotka
14330