2026-07-20T15:08:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2350 2024-03-06T10:28:41Z ddc:004 open_access

The Parameterized Complexity of Oriented Colouring Ganian, Robert Oriented colouring tree-width rank-width parameterized algorithms graphs 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 treat 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Ganian 2009 Is Part Of OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DROPS.MEMICS.2009.2350 urn:nbn:de:0030-drops-23500 https://drops.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2350 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode