New results on the complexity of oriented colouring on restricted digraph classes
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F10%3A00044259" target="_blank" >RIV/00216224:14330/10:00044259 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/00216224:14330/10:00065874
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
New results on the complexity of oriented colouring on restricted digraph classes
Popis výsledku v původním jazyce
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 tacklingthis 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 problemon digraphs of bounded K-width and of bounded DAG-depth.
Název v anglickém jazyce
New results on the complexity of oriented colouring on restricted digraph classes
Popis výsledku anglicky
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 tacklingthis 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 problemon digraphs of bounded K-width and of bounded DAG-depth.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2010
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
SOFSEM 2010, Lecture Notes in Computer Science 5901
ISBN
978-3-642-11265-2
ISSN
—
e-ISSN
—
Počet stran výsledku
12
Strana od-do
—
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Špindlerův mlýn
Datum konání akce
1. 1. 2010
Typ akce podle státní příslušnosti
EUR - Evropská akce
Kód UT WoS článku
000280086900036