The Parameterized Complexity of Oriented Colouring

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert

Year of publication 2009
Type Article in Proceedings
Conference MEMICS 2009 proceedings
MU Faculty or unit

Faculty of Informatics

Citation
Web http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=2342
Field Information theory
Keywords Oriented colouring; Parameterized complexity; digraphs; directed graphs; width measures
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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info