![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
DAG-width - Connectivity Measure for Directed Graphs
Název česky | DAG-width - míra spojitosti pro orientované grafy |
---|---|
Autoři | |
Rok publikování | 2006 |
Druh | Článek ve sborníku |
Konference | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
Fakulta / Pracoviště MU | |
Citace | |
Obor | Obecná matematika |
Klíčová slova | tree-width; directed tree-width; DAG-width; digraph-searching |
Popis | Tree-width je velmi užitečná míra souvislosti pro neorientované grafy. Navrhujeme novou definici, nazvanou DAG-width, pro orientované grafy, která měří jak blízko je daný graf orientovanému acyklickému grafu. Dále definujeme novou hru typu "četníci a zloděj" a ukážeme že tato hra charakterizuje přesně grafy s omezenou DAG-width. Dále následuje porovnání DAG-width s tree-width a directed tree-width. Nakonec ukážeme že NP-úplné problémy mohou být řešeny v polynomiálním čase na grafech s omezenou DAG-width. |