Complexity of searching an immobile hider in a graph
From MaRDI portal
Publication:1377669
DOI10.1016/S0166-218X(97)00011-5zbMath0890.68105MaRDI QIDQ1377669
Ralph Werchner, Bernhard von Stengel
Publication date: 23 June 1998
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://www.elsevier.com/locate/dam
Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
A competitive search game with a moving target, Scheduling search procedures: The wheel of fortune, On Submodular Search and Machine Scheduling, Search Games: A Review, Search for an immobile entity on a network, Network search games with immobile hider, without a designated searcher starting point, The expanding search ratio of a graph, Searching symmetric networks with Utilitarian-Postman paths, Search for an immobile hider on a stochastic network, Ranking hypotheses to minimize the search cost in probabilistic inference models, Searching a Variable Speed Network
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal search with positive switch cost is NP-hard
- Matching theory
- Search-hide games on trees
- Search games
- Geometric algorithms and combinatorial optimization
- Inspection games in arms control
- Color-coding
- The complexity of searching a graph
- Pursuit—Evasion games on graphs
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- Discrete Sequential Search with Positive Switch Cost
- Monotonicity in graph searching
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- Technical Note—The Complexity of the Optimal Searcher Path Problem
- Properties of vertex packing and independence system polyhedra
