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

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, 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 http://dx.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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.