Monotonicity of strong searching on digraphs
From MaRDI portal
Publication:2426650
DOI10.1007/s10878-007-9042-zzbMath1149.90168MaRDI QIDQ2426650
Publication date: 23 April 2008
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-007-9042-z
NP-complete; Monotonicity; Digraph; Cops-and-robber game; Graph searching; Pursuit-and-evasion problem
90C35: Programming involving graphs or networks
90C60: Abstract computational complexity for mathematical programming problems
91A24: Positional games (pursuit and evasion, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Digraph searching, directed vertex separation and directed pathwidth
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- Searching and pebbling
- Directed tree-width
- Directed path-width and monotonicity in digraph searching
- Directed tree-width examples
- DAG-width
- The complexity of searching a graph
- Monotonicity in graph searching
- Recontamination does not help to search a graph
- Eavesdropping games
- DAG-Width and Parity Games