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. |