Graph searching games and width measures for directed graphs

DOI10.4230/LIPICS.STACS.2015.34MaRDI QIDQ2954982zbMATH OpenFDO

Authors Saeed Akhoondian Amiri, Łukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz

Publication date 24 January 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2015.34

zbMATH Keywords

cops and robber gamesDAG-widthdirected graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Recommendations

• The dag-width of directed graphs
• DAG-Width and Parity Games
• Directed path-width and monotonicity in digraph searching
• Are there any good digraph width measures?
• Directed tree-width examples

Cited in

(13)

• Directed width parameters on semicomplete digraphs
• How to compute digraph width measures on directed co-graphs
• Static search games played over graphs and general metric spaces
• Directed path-width and monotonicity in digraph searching
• Directed tree-width examples
• An algorithmic metatheorem for directed treewidth
• LIFO-search on digraphs: a searching game for cycle-rank
• Digraphs of bounded width
• DAG-width is PSPACE-complete
• The dag-width of directed graphs
• scientific article; zbMATH DE number 7559442 (Why is no real title available?)
• DAG-Width and Parity Games
• Twin-distance-hereditary digraphs

This page was built for publication: Graph searching games and width measures for directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2954982)