License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DROPS.MEMICS.2009.2350
URN: urn:nbn:de:0030-drops-23500
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2350/
Go to the corresponding OASIcs Volume Portal

Ganian, Robert

The Parameterized Complexity of Oriented Colouring

pdf-format:
09006.GanianRobert.2350.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{ganian:OASIcs:2009:2350,
  author =	{Robert Ganian},
  title =	{{The Parameterized Complexity of Oriented Colouring}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{86--93},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Petr Hlinen{\'y} and V{\'a}clav Maty{\'a}{\v{s}} and Tom{\'a}{\v{s}} Vojnar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2350},
  URN =		{urn:nbn:de:0030-drops-23500},
  doi =		{10.4230/DROPS.MEMICS.2009.2350},
  annote =	{Keywords: Oriented colouring, tree-width, rank-width, parameterized algorithms, graphs}
}

Keywords: Oriented colouring, tree-width, rank-width, parameterized algorithms, graphs
Collection: Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)
Issue Date: 2009
Date of publication: 15.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI