Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{890230,
author = {Ganian, Robert},
address = {Dagstuhl, Germany},
booktitle = {MEMICS 2009 proceedings},
keywords = {Oriented colouring; Parameterized complexity; digraphs; directed graphs; width measures},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-939897-15-6},
publisher = {DROPS},
title = {The Parameterized Complexity of Oriented Colouring},
url = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=2342},
year = {2009}
}
TY - JOUR
ID - 890230
AU - Ganian, Robert
PY - 2009
TI - The Parameterized Complexity of Oriented Colouring
PB - DROPS
CY - Dagstuhl, Germany
SN - 9783939897156
KW - Oriented colouring
KW - Parameterized complexity
KW - digraphs
KW - directed graphs
KW - width measures
UR - http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=2342
N2 - 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.
ER -
GANIAN, Robert. The Parameterized Complexity of Oriented Colouring. In \textit{MEMICS 2009 proceedings}. Dagstuhl, Germany: DROPS, 2009, 8 s. ISBN~978-3-939897-15-6.
|
