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; 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
• 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

• 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