Escape-width: Measuring "width" of digraphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Conference abstract |
| MU Faculty or unit | |
| 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: |