Další formáty:
BibTeX
LaTeX
RIS
@proceedings{706398, author = {Hliněný, Petr and Obdržálek, Jan}, booktitle = {Combinatorics, Graph Theory, Algorithms and Applications. Abstracts}, language = {eng}, title = {Escape-width: Measuring "width" of digraphs}, url = {http://kam.mff.cuni.cz/~cs06/}, year = {2006} }
TY - CONF ID - 706398 AU - Hliněný, Petr - Obdržálek, Jan PY - 2006 TI - Escape-width: Measuring "width" of digraphs UR - http://kam.mff.cuni.cz/~cs06/ N2 - The question of finding an extension of the ordinary tree-width notion to directed graphs, with similarly nice algorithmic properties, seems to be a challenging problem. Nowadays there exist two competing extensions -- the older directed tree-width by Johnson, Robertson, Seymour, and Thomas, and the recent DAG-width which has been independently proposed by the second author and Berwanger, Dawar, Hunter and Kreutzer. In this paper we introduce yet another extension that naturally arises by introducing orientation of edges in one of alternative definitions of ordinary tree-width, and we show that it is closely related to DAG-width. ER -
HLINĚNÝ, Petr a Jan OBDRŽÁLEK. Escape-width: Measuring ''width'' of digraphs. In \textit{Combinatorics, Graph Theory, Algorithms and Applications. Abstracts}. 2006.
|