Journal article icon

Journal article

Digraph measures: Kelly decompositions, games, and orderings

Abstract:

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 p...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.1016/j.tcs.2008.02.038

Authors


More by this author
Institution:
University of Cambridge
More by this author
Institution:
University of Oxford
Department:
Mathematical, Physical & Life Sciences Division - Department of Computer Science
Publisher:
Elsevier Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
399
Issue:
3
Pages:
206–219
Publication date:
2008-06-05
DOI:
ISSN:
0304-3975
URN:
uuid:6dd728d5-d2f7-4911-9499-3e76990cff4b
Local pid:
ora:10786

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP