Symposium on Discrete Algorithms · 2006 · 85 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationDirected Acyclic GraphsGraph AlgorithmsGraph TheoryAlgorithmic Graph TheoryComplete ProblemsComputational Complexity Of Graph AlgorithmsGraph GamesNp-complete ProblemsPolynomial Time ComplexityPolynomial-time AlgorithmsTree Diameter
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.
7
Thor Johnson, Neil Robertson, Paul Seymour et al. · Journal of Combinatorial Theory Series B · 2001 · 274 citations