Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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-26. doi:10.1016/j.tcs.2018.06.022 ISSN 0304-3975.

[img]
Preview
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

Request Changes to record.

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:
DateEvent
19 November 2019Published
21 June 2018Available
12 June 2018Accepted
Volume: 794
Page Range: pp. 20-26
DOI: 10.1016/j.tcs.2018.06.022
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 13 June 2018
Date of first compliant Open Access: 21 June 2019
Related URLs:
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us