Search and delivery man problems: when are depth-first paths optimal?

DOI10.1016/j.ejor.2020.02.026zbMath1443.90203arXiv1910.13178MaRDI QIDQ2184055

Thomas F. Lidbetter, Steven Alpern

Publication date: 27 May 2020

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.13178

zbMATH Keywords

networks; trees; depth-first search; delivery man problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90B40: Search theory

91A43: Games involving graphs

91A24: Positional games (pursuit and evasion, etc.)

Cites Work

• Unnamed Item
• A new approach to Gal's theory of search games on weakly Eulerian networks
• The delivery man problem on a tree network
• Network search games with immobile hider, without a designated searcher starting point
• Search games
• Star search -- a different show
• An improved approximation ratio for the minimum latency problem
• The theory of search games and rendezvous.
• Search games and other applications of game theory
• A search problem on a bipartite network
• Finding a hider by an unknown deadline
• Generalizations in the linear search problem
• On the linear search problem
• More on the linear search problem
• The minimum latency problem
• Search Games with Multiple Hidden Objects
• Searching symmetric networks with Utilitarian-Postman paths
• Search Games on Trees with Asymmetric Travel Times
• Network search games, with arbitrary searcher starting point
• The Revenge of the Linear Search Problem
• Search Games with Mobile and Immobile Hider
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• Approximation Schemes for Minimum Latency Problems
• Hide-and-Seek Games on a Network, Using Combinatorial Search Paths
• On Submodular Search and Machine Scheduling
• Multiple searchers searching for a randomly distributed immobile target on a unit network
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• Searching a Variable Speed Network
• Mining Coal or Finding Terrorists: The Expanding Search Paradigm
• Search games on networks with travelling and search costs and with arbitrary searcher starting points
• An Optimal Search Problem