The mixed search game against an agile and visible fugitive is monotone

DOI10.1016/j.disc.2023.113345MaRDI QIDQ2685344

Guillaume Mescoff, Dimitrios M. Thilikos, Christophe Paul

Publication date: 21 February 2023

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

Full work available at URL: https://arxiv.org/abs/2204.10691

zbMATH Keywords

tree decomposition; bramble; Cartesian tree product number; graph searching game

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P10: Searching and sorting

91A05: 2-person games

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

91A24: Positional games (pursuit and evasion, etc.)

05C57: Games on graphs (graph-theoretic aspects)

05C76: Graph operations (line graphs, products, etc.)

Cites Work

• Unnamed Item
• Unnamed Item
• Mixed searching and proper-path-width
• Graph minors. III. Planar tree-width
• Monotonicity of non-deterministic graph searching
• An annotated bibliography on guaranteed graph searching
• Partitions versus sets: a case of duality
• Submodular partition functions
• Quickly excluding a forest
• The vertex separation number of a graph equals its path-width
• S-functions for graphs
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• On the monotonicity of games generated by symmetric submodular functions.
• Multiplicities of eigenvalues and tree-width of graphs
• Searching and pebbling
• Monotonicity in graph searching