The expanding search ratio of a graph
type: Item
instance of: scholarly article
title: The expanding search ratio of a graph
zbMATH Open document ID: 1425.90123
author: Spyros Angelopoulos
author: Christoph Dürr
author: Thomas Lidbetter
published in: Discrete Applied Mathematics
publication date: 2019-05-03T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5710/
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 7050988
zbMATH Keywords: search games
zbMATH Keywords: competitive analysis
zbMATH Keywords: game theory
zbMATH Keywords: randomized algorithms
zbMATH Keywords: graph search
MaRDI profile type: Publication
OpenAlex ID: W2963470234
cites work: Network search games with immobile hider, without a designated searcher starting point
cites work: Mining Coal or Finding Terrorists: The Expanding Search Paradigm
cites work: The expanding search ratio of a graph
cites work: Multi-target ray searching problems
cites work: Approximation Schemes for Minimum Latency Problems
cites work: Q4503935
cites work: Searching in the plane
cites work: Search games on networks with travelling and search costs and with arbitrary searcher starting points
cites work: Search games on a network with travelling and search costs
cites work: On the linear search problem
cites work: Yet more on the linear search problem
cites work: The minimum latency problem
cites work: Searching on a line: a complete characterization of the optimal solution
cites work: An improved LP-based approximation for Steiner tree
cites work: Algorithms for distributional and adversarial pipelined filter ordering problems
cites work: Network search games, with arbitrary searcher starting point
cites work: Online searching with turn cost
cites work: Competitive Online Approximation of the Optimal Search Ratio
cites work: A general search game
cites work: Minimax Solutions for Linear Search Problems
cites work: Search Games with Mobile and Immobile Hider
cites work: On the optimality of a simple strategy for searching graphs
cites work: An improved approximation ratio for the minimum latency problem
cites work: Optimal Constructions of Hybrid Algorithms
cites work: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
cites work: Hyperbolic Dovetailing
cites work: Q4818841
cites work: Search games with multiple hidden objects
cites work: The ultimate strategy to search on \(m\) rays?
cites work: On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
cites work: The Oil Searching Problem
cites work: A search game on the union of graphs with immobile hider
cites work: Search games with immobile hider
cites work: Q4413802
cites work: Q4737530
cites work: Complexity of searching an immobile hider in a graph
Wikidata QID: Q128319106
DOI: 10.1016/J.DAM.2019.01.039
description: scientific article; zbMATH DE number 7050988