LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth

DOI10.1016/J.DAM.2012.03.015MaRDI QIDQ713301zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, Paul Hunter, Dimitrios M. Thilikos

Publication date 26 October 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.03.015

zbMATH Keywords

tree-depthobstructionsgraph parametersgraph searchingpursuit-evasion gamesmin-max theoremcycle-rank

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Evolutionary games (91A22)

Recommendations

• A min-max theorem for LIFO-search
• LIFO-search on digraphs: a searching game for cycle-rank
• Fugitive-search games on graphs and related parameters
• scientific article; zbMATH DE number 176249
• Monotonicity and inert fugitive search games

Cites work

• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• A min-max theorem for LIFO-search
• DAG-Width and Parity Games
• DAG-width
• Digraph Decompositions and Monotonicity in Digraph Searching
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Directed tree-width examples
• Fugitive-search games on graphs and related parameters
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Graph searching and a min-max theorem for tree-width
• LIFO-search on digraphs: a searching game for cycle-rank
• Linear time low tree-width partitions and algorithmic consequences
• Mathematical Foundations of Computer Science 2005
• Monotonicity in graph searching
• On digraph width measures in parameterized algorithmics
• Optimal edge ranking of trees in polynomial time
• Ordered colourings
• Rankings of Graphs
• Recontamination does not help to search a graph
• Searching and pebbling
• The Theory of Elimination Trees for Sparse Unsymmetric Matrices
• Transition graphs and the star-height of regular events
• Tree-depth, subgraph coloring and homomorphism bounds

Cited in

(9)

• A graph searching game for block treedepth and a cubic kernel by vertex cover
• Edge and pair queries-random graphs and complexity
• scientific article; zbMATH DE number 7764119 (Why is no real title available?)
• Compact representation of graphs with bounded bandwidth or treedepth
• On low tree-depth decompositions
• LIFO-search on digraphs: a searching game for cycle-rank
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• List rankings and on-line list rankings of graphs

This page was built for publication: LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth

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