Digraph measures: Kelly decompositions, games, and orderings

Journal article

We consider various well-known, equivalent complexity measures for graphs such as elimination orderings, k-trees and cops and robber games and study their natural translations to digraphs. We show that on digraphs the translations of these measures are also equivalent and induce a natural connectivity measure. We introduce a decomposition for digraphs and an associated width, Kelly-width, which is equivalent to the aforementioned measure. We demonstrate its usefulness by exhibiting potential applications including polynomial-time algorithms for NP-complete problems on graphs of bounded Kelly-width, and complexity analysis of asymmetric matrix factorization. Finally, we compare the new width to other known decompositions of digraphs.

Authors: Hunter, P; Kreutzer, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 399
• Issue: 3
• Pages: 206–219
• Publication date: 2008-06-01
• Edition: Publisher's version
• DOI: 10.1016/j.tcs.2008.02.038
• ISSN: 0304-3975
• Language: English
• Keywords: cop and robber games; graph decompositions; directed graphs
• Subjects: Game semantics