Publication details
DAG-width - Connectivity Measure for Directed Graphs
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Proceedings |
| Conference | Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| MU Faculty or unit | |
| Citation | |
| Field | General mathematics |
| Keywords | tree-width; directed tree-width; DAG-width; digraph-searching |
| Description | 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. |