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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Nové výsledky o složitosti orientovaného barvení na omezených třídách grafů
Autoři	GANIAN Robert HLINĚNÝ Petr
Rok publikování	2010
Druh	Článek ve sborníku
Konference	SOFSEM 2010, Lecture Notes in Computer Science 5901
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	DOI
Doi	https://doi.org/10.1007/978-3-642-11266-9_36
Obor	Informatika
Klíčová slova	Directed graph; complexity; oriented colouring; DAG-depth
Popis	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.
Související projekty:	Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti Strukturální teorie grafů a parametrizovaná složitost Parameterized Algorithms and Width measures on Graphs Rozsáhlé výpočetní systémy: modely, aplikace a verifikace