Monotonicity of strong searching on digraphs

DOI10.1007/s10878-007-9042-zzbMath1149.90168OpenAlexW2076965738MaRDI QIDQ2426650

Yi Cao, Boting Yang

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

zbMATH Keywords

NP-completeMonotonicityDigraphCops-and-robber gameGraph searchingPursuit-and-evasion problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Positional games (pursuit and evasion, etc.) (91A24)

Related Items (1)

Monotonicity in digraph search problems

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

This page was built for publication: Monotonicity of strong searching on digraphs