New results on the complexity of oriented colouring on restricted digraph classes
The result's identifiers
Result code in 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>
Alternative codes found
RIV/00216224:14330/10:00065874
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
New results on the complexity of oriented colouring on restricted digraph classes
Original language 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 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
S - Specificky vyzkum na vysokych skolach
Others
Publication year
2010
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
SOFSEM 2010, Lecture Notes in Computer Science 5901
ISBN
978-3-642-11265-2
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer
Place of publication
Berlin
Event location
Špindlerův mlýn
Event date
Jan 1, 2010
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
000280086900036