The Parameterized Complexity of Oriented Colouring

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F09%3A00044284" target="_blank" >RIV/00216224:14330/09:00044284 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

The Parameterized Complexity of Oriented Colouring

Original language description

The oriented colouring problem is intuitive and related to undirected colouring, yet remains NP-hard even on digraph classes with bounded traditional directed width measures. Recently we have also proved that it remains NP-hard in otherwise severely restricted digraph classes. However, unlike most other problems on directed graphs, the oriented colouring problem is not directly transferable to undirected graphs. In the article we look at the parameterized complexity of computing the oriented colouring of digraphs with bounded undirected width parameters, whereas the parameters "forget" about the orientations of arcs and parse them as edges. Specifically, we provide new complexity results for computing oriented colouring on digraphs of bounded undirected rank-width and a new algorithm for this problem on digraphs of bounded undirected tree-width.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

BD - Information theory

OECD FORD branch

—

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2009

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

MEMICS 2009 proceedings

ISBN

978-3-939897-15-6

ISSN

—

e-ISSN

—

Number of pages

8

Pages from-to

—

Publisher name

DROPS

Place of publication

Dagstuhl, Germany

Event location

Znojmo

Event date

Jan 1, 2009

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—