The Parameterized Complexity of Oriented Colouring

Author Robert Ganian



PDF
Thumbnail PDF

File

DROPS.MEMICS.2009.2350.pdf
  • Filesize: 457 kB
  • 8 pages

Document Identifiers

Author Details

Robert Ganian

Cite AsGet BibTex

Robert Ganian. The Parameterized Complexity of Oriented Colouring. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 88-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DROPS.MEMICS.2009.2350

Abstract

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.
Keywords
  • Oriented colouring
  • tree-width
  • rank-width
  • parameterized algorithms
  • graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail