On Digraph Width Measures in Parameterized Algorithmics

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	O orientovaných šířkových parametrech v parametrizovaných algoritmech
Autoři	GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan LANGER Alexander KNEIS Joachim ROSSMANITH Peter
Rok publikování	2009
Druh	Článek ve sborníku
Konference	IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	Conference DOI
Doi	https://doi.org/10.1007/978-3-642-11269-0_15
Obor	Informatika
Klíčová slova	digraph; DAG-width; bi-rank-width; parameterized complexity
Popis	Rozebíráme obšírně důvody, proč orientované analogie klasických šířkových parametrů grafů nedávají uspokojivé algoritmické výsledky.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti Strukturální teorie grafů a parametrizovaná složitost