An annotated bibliography on guaranteed graph searching

DOI10.1016/j.tcs.2008.02.040zbMath1160.68007OpenAlexW2106518318WikidataQ60488721 ScholiaQ60488721MaRDI QIDQ930895

Fedor V. Fomin, Dimitrios M. Thilikos

Publication date: 24 June 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.040

zbMATH Keywords

graph searching cops and robbers games fugitive search games pursuit evasion in graphs

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (only showing first 100 items - show all)

A symbolic programming approach to the rendezvous search problem ⋮ Complexity and monotonicity results for domination games ⋮ Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ General cops and robbers games with randomness ⋮ Intruder alert! Optimization models for solving the mobile robot graph-clear problem ⋮ Variations on cops and robbers ⋮ Localization game on geometric and planar graphs ⋮ Contraction obstructions for connected graph searching ⋮ On the monotonicity of process number ⋮ The cost of monotonicity in distributed graph searching ⋮ Searching for an intruder on graphs and their subdivisions ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ Jumping robbers in digraphs ⋮ Collision-free network exploration ⋮ Cops and robbers from a distance ⋮ Parameterized pursuit-evasion games ⋮ Cops and invisible robbers: the cost of drunkenness ⋮ The guarding game is E-complete ⋮ Locating a robber on a graph via distance queries ⋮ Approximate search strategies for weighted trees ⋮ \textsc{polish} -- Let us play the cleaning game ⋮ Some remarks on cops and drunk robbers ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ A local strategy for cleaning expanding cellular domains by simple robots ⋮ Evacuating two robots from multiple unknown exits in a circle ⋮ Lions and contamination: monotone clearings ⋮ How to hunt an invisible rabbit on a graph ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ Directed elimination games ⋮ Fast searching games on graphs ⋮ Fast Searching on Complete k-partite Graphs ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ Edge search number of cographs ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ Almost all cop-win graphs contain a universal vertex ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Edge degeneracy: algorithmic and structural results ⋮ A distributed algorithm for computing the node search number in trees ⋮ Network decontamination under \(m\)-immunity ⋮ Fast searching on cactus graphs ⋮ Tradeoffs in process strategy games with application in the WDM reconfiguration problem ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ To satisfy impatient web surfers is hard ⋮ Priority evacuation from a disk: the case of \(n \geq 4\) ⋮ The theory of guaranteed search on graphs ⋮ Guard games on graphs: keep the intruder out! ⋮ Three-fast-searchable graphs ⋮ How to guard a graph? ⋮ Fast Searching on Cartesian Products of Graphs ⋮ CADbots: algorithmic aspects of manipulating programmable matter with finite automata ⋮ Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning ⋮ The complexity of minimum-length path decompositions ⋮ Computing on rings by oblivious robots: a unified approach for different tasks ⋮ Four-searchable biconnected outerplanar graphs ⋮ Monotonicity in digraph search problems ⋮ A unified approach for gathering and exclusive searching on rings under weak assumptions ⋮ Cooperative exploration and protection of a workspace assisted by information networks ⋮ Exclusive graph searching ⋮ On mobile agent verifiable problems ⋮ Linear search by a pair of distinct-speed robots ⋮ The fast search number of a Cartesian product of graphs ⋮ Connected graph searching ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Quiescence of self-stabilizing gossiping among mobile agents in graphs ⋮ Cops and robber game without recharging ⋮ On some problems of guaranteed search on graphs ⋮ Cop-win graphs with maximum capture-time ⋮ A graph search algorithm for indoor pursuit/evasion ⋮ Pursuing a fast robber on a graph ⋮ Locating a robber on a graph ⋮ CSP duality and trees of bounded pathwidth ⋮ Characterization of graphs and digraphs with small process numbers ⋮ Connected searching of weighted trees ⋮ Security and Formation of Network-Centric Operations ⋮ Safe navigation in adversarial environments ⋮ Chasing robbers on random graphs: Zigzag theorem ⋮ Large classes of infinite k-cop-win graphs ⋮ Meyniel's conjecture holds for random graphs ⋮ Beachcombing on strips and islands ⋮ Exclusive graph searching vs. pathwidth ⋮ Monotony properties of connected visible graph searching ⋮ The fast search number of a complete \(k\)-partite graph ⋮ Chasing robbers on random geometric graphs-an alternative approach ⋮ Pursuit of a Moving Target with Known Constant Speed on a Directed Acyclic Graph under Partial Information ⋮ Some game-theoretic remarks on two-player generalized cops and robbers games ⋮ A pursuit-evasion differential game with slow pursuers on the edge graph of a simplex. I ⋮ Linear Search by a Pair of Distinct-Speed Robots ⋮ On Rerouting Connection Requests in Networks with Shared Bandwidth ⋮ Lions and contamination, triangular grids, and Cheeger constants ⋮ Hyperopic cops and robbers ⋮ Finding small-width connected path decompositions in polynomial time ⋮ The capture time of a graph ⋮ Digraphs of Bounded Width ⋮ Zero-visibility cops and robber and the pathwidth of a graph ⋮ Non-deterministic graph searching in trees ⋮ The searchlight problem for road networks ⋮ Distributed graph searching with a sense of direction ⋮ A game theoretic analysis of the cops and robber game ⋮ The localization capture time of a graph

Cites Work

This page was built for publication: An annotated bibliography on guaranteed graph searching