The Library
Search for an immobile Hider in a known subset of a network
Tools
Tools
Tools
Alpern, Steve (2019) Search for an immobile Hider in a known subset of a network. Theoretical Computer Science, 794 . pp. 20-60. doi:10.1016/j.tcs.2018.06.022 (In Press)
|
PDF
WRAP-search-immobile-Hider-known-network-Alpern-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (470Kb) | Preview |
Official URL: https://doi.org/10.1016/j.tcs.2018.06.022
Abstract
A unit speed Searcher, constrained to start in a given closed set S, wishes to quickly find a point x known to be located in a given closed subset H of a metric network Q. This defines a game G=G(Q,H,S), where the payoff to the maximizing Hider is the time for the Searcher path to reach x. Lengths on Q are defined by a measure λ, which then defines distance as least length of connecting path. For trees Q, we find that the minimax search time (value V of G) is given by V=λ(H)-d_{H}(S)/2, where d_{H}(S) is what we call the `H-diameter of S', and equals the usual diameter d(S) of S in the case H=Q. For the classical case of Gal where the S is a singleton and H=Q, our formula reduces to his result V=λ(Q). If S=H=Q, our formula gives Dagan and Gal's result V=λ(Q)-d(Q)/2. In all other cases, our result is new. Optimal searches consist of minimum length paths covering H which start and end at points of S, traversed equiprobably in either direction.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
| Divisions: | Faculty of Social Sciences > Warwick Business School > Operational Research & Management Sciences Faculty of Social Sciences > Warwick Business School |
||||||||
| Library of Congress Subject Headings (LCSH): | Two-person zero-sum games | ||||||||
| Journal or Publication Title: | Theoretical Computer Science | ||||||||
| Publisher: | Elsevier Science BV | ||||||||
| ISSN: | 0304-3975 | ||||||||
| Official Date: | 19 November 2019 | ||||||||
| Dates: |
|
||||||||
| Date of first compliant deposit: | 13 June 2018 | ||||||||
| Volume: | 794 | ||||||||
| Page Range: | pp. 20-60 | ||||||||
| DOI: | 10.1016/j.tcs.2018.06.022 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | In Press | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
