New results on the complexity of oriented colouring on restricted digraph classes

GANIAN, Robert a Petr HLINĚNÝ. New results on the complexity of oriented colouring on restricted digraph classes. Online. In SOFSEM 2010, Lecture Notes in Computer Science 5901. 5901. vyd. Berlin: Springer, 2010. s. 428-439. ISBN 978-3-642-11265-2. Dostupné z: https://dx.doi.org/10.1007/978-3-642-11266-9_36. [citováno 2024-04-24]

Základní údaje

• Originální název: New results on the complexity of oriented colouring on restricted digraph classes
• Název česky: Nové výsledky o složitosti orientovaného barvení na omezených třídách grafů
• Autoři: GANIAN, Robert (840 Spojené státy, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí)
• Vydání: 5901. vyd. Berlin, SOFSEM 2010, Lecture Notes in Computer Science 5901, od s. 428-439, 12 s. 2010.
• Nakladatel: Springer

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Česká republika
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: tištěná verze "print"
• WWW: DOI
• Impakt faktor: Impact factor: 0.402 v roce 2005
• Kód RIV: RIV/00216224:14330/10:00065874
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-3-642-11265-2
• ISSN: 0302-9743
• Doi: http://dx.doi.org/10.1007/978-3-642-11266-9_36
• UT WoS: 000280086900036
• Klíčová slova anglicky: Directed graph; complexity; oriented colouring; DAG-depth
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

Oriented colouring is a quite intuitive generalization of undirected colouring, yet the problem remains NP-hard even on digraph classes with bounded usual directed width measures. In light of this fact, one might ask whether new width measures are required for efficient dealing with this problem or whether further restriction of traditional directed width measures such as DAG-width would suffice. The K-width and DAG-depth measures (introduced by [Ganian et al, IWPEC09]) are ideal candidates for tackling this question: They are both closely tied to the cops-and-robber games which inspire and characterize the most renowned directed width measures, while at the same time being much more restrictive. In this paper, we look at the oriented colouring problem on digraphs of bounded K-width and of bounded DAG-depth. We provide new polynomial algorithms for solving the problem on small instances as well as new strong hardness results showing that the input restrictions required by our algorithms are in fact tight.

Anotace česky

Orientované barvení grafů přirozeně zobecňuje neorientované barvení, ale problém zůstává těžký i na grafech s omezenými šířkovými mírami. V článku studujeme složitost tohoto problému na orientovaných grafech malé DAG-depth a K-width, našich nových šířkových mírách.

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