The Parameterized Complexity of Oriented Colouring

GANIAN, Robert. The Parameterized Complexity of Oriented Colouring. In MEMICS 2009 proceedings. Dagstuhl, Germany: DROPS, 2009, 8 s. ISBN 978-3-939897-15-6.

Základní údaje

Originální název

The Parameterized Complexity of Oriented Colouring

Autoři

GANIAN, Robert

Vydání

Dagstuhl, Germany, MEMICS 2009 proceedings, 8 s. 2009

Nakladatel

DROPS

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10000 1. Natural Sciences

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14330/09:00044284

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-15-6

Klíčová slova anglicky

Oriented colouring; Parameterized complexity; digraphs; directed graphs; width measures

Štítky

parameterized algorithm, rank-width

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

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.

---

Návaznosti

GA201/08/0308, projekt VaV	Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti
GC201/09/J021, projekt VaV	Název: Strukturální teorie grafů a parametrizovaná složitost Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost
MUNI/A/0914/2009, interní kód MU	Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV) Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/E/0059/2009, interní kód MU	Název: Parameterized Algorithms and Width measures on Graphs Investor: Masarykova univerzita, Parameterized Algorithms and Width measures on Graphs, Kat. E - Podpora výzkumné činnosti studentů v oborech lékařství, zdravotnictví, přírodovědy a informatiky - rozvojový projekt + specifický výzkum