Escape-width: Measuring "width" of digraphs

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr OBDRŽÁLEK Jan

Year of publication 2006
Type Conference abstract
MU Faculty or unit

Faculty of Informatics

Citation
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.