On Digraph Width Measures in Parameterized Algorithmics

• 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

www

• Conference
• DOI

• Doi: http://dx.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