2006
DAG-width - Connectivity Measure for Directed Graphs
OBDRŽÁLEK, JanZákladní údaje
Originální název
DAG-width - Connectivity Measure for Directed Graphs
Název česky
DAG-width - míra spojitosti pro orientované grafy
Autoři
Vydání
New York/Philadelphia, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, od s. 814--821, 8 s. 2006
Nakladatel
Association for Computing Machinery/Society for Industrial and Applied Mathematics
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10101 Pure mathematics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Kód RIV
RIV/00216224:14330/06:00016845
Organizační jednotka
Fakulta informatiky
ISBN
0-89871-605-5
UT WoS
000281596300090
Klíčová slova anglicky
tree-width; directed tree-width; DAG-width; digraph-searching
Změněno: 15. 3. 2010 08:49, doc. Mgr. Jan Obdržálek, PhD.
V originále
Tree-width is a very useful connectivity measure for undirected graphs. We propose a new definition, called DAG-width, for directed graphs which measures how close a graph is to a directed acyclic graph. In addition we define a cops-and-robber game and show that this game characterises exactly the class of graphs of bounded DAG-width. A comparison of DAG-width with tree-width and directed tree-width follows. Finally we show that NP-complete problems can be solved in polynomial time on graphs of bounded DAG-width.
Česky
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.
Návaznosti
| MSM0021620808, záměr |
|