The expanding search ratio of a graph
From MaRDI portal
Publication:1741496
DOI10.1016/j.dam.2019.01.039zbMath1425.90123OpenAlexW2963470234WikidataQ128319106 ScholiaQ128319106MaRDI QIDQ1741496
Christoph Dürr, Spyros Angelopoulos, Thomas F. Lidbetter
Publication date: 3 May 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5710/
Related Items
Further connections between contract-scheduling and ray-searching problems, Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract), Online routing and searching on graphs with blocked edges, Exact and Approximation Algorithms for the Expanding Search Problem, Search and rescue in the face of uncertain threats, Competitive search in a network, Evacuating from \(\ell_p\) unit disks in the wireless model, Weighted online search, Algorithms for \(p\)-Faulty Search on a half-line, Online search with a hint, Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games, A game theoretic approach to a problem in polymatroid maximization, Weighted group search on a line \& implications to the priority evacuation problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
- Searching in the plane
- Network search games with immobile hider, without a designated searcher starting point
- An improved approximation ratio for the minimum latency problem
- Complexity of searching an immobile hider in a graph
- On the optimality of a simple strategy for searching graphs
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- Search games on a network with travelling and search costs
- Search games with immobile hider
- Multi-target ray searching problems
- Online searching with turn cost
- Searching on a line: a complete characterization of the optimal solution
- On the linear search problem
- Yet more on the linear search problem
- A general search game
- The minimum latency problem
- Search Games with Multiple Hidden Objects
- An improved LP-based approximation for steiner tree
- Network search games, with arbitrary searcher starting point
- Competitive Online Approximation of the Optimal Search Ratio
- The Oil Searching Problem
- Hyperbolic Dovetailing
- Minimax Solutions for Linear Search Problems
- Search Games with Mobile and Immobile Hider
- Optimal Constructions of Hybrid Algorithms
- Approximation Schemes for Minimum Latency Problems
- The expanding search ratio of a graph
- A search game on the union of graphs with immobile hider
- Algorithms for distributional and adversarial pipelined filter ordering problems
- Mining Coal or Finding Terrorists: The Expanding Search Paradigm
- Search games on networks with travelling and search costs and with arbitrary searcher starting points
- The ultimate strategy to search on \(m\) rays?
