A game of cops and robbers
From MaRDI portal
Publication:793755
DOI10.1016/0166-218X(84)90073-8zbMath0539.05052OpenAlexW2046635105MaRDI QIDQ793755
Publication date: 1984
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(84)90073-8
Structural characterization of families of graphs (05C75) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)
Related Items
Variations on cops and robbers, A Leapfrog Strategy for Pursuit-Evasion in a Polygonal Environment, Subdivisions in the robber locating game, Unnamed Item, Fast Robber in Planar Graphs, On Meyniel's conjecture of the cop number, Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond, TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS, Cop-Robber Guarding Game with Cycle Robber Region, A uniform betweenness property in metric spaces and its role in the quantitative analysis of the ``lion-man game, The damage throttling number of a graph, On Strict (Outer-)Confluent Graphs, Cops and an insightful robber, Chasing a Fast Robber on Planar Graphs and Random Graphs, An Introduction to Lazy Cops and Robbers on Graphs, Reasoning About Strategies, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Spy game: FPT-algorithm, hardness and graph products, Cops and Robbers on Dynamic Graphs: Offline and Online Case, On the contractibility of random Vietoris-Rips complexes, On the cop number of graphs of high girth, On the Capture Time of Cops and Robbers Game on a Planar Graph, Cops and robber on oriented graphs with respect to push operation, Cops and robber on butterflies, grids, and AT-free graphs, Cops \& robber on periodic temporal graphs: characterization and improved bounds, Smarter Lions: Efficient Cooperative Pursuit in General Bounded Arenas, Learning through imitation by using formal verification, A note on hyperopic cops and robber, On colourability of polygon visibility graphs, Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs, Lazy Cops and Robbers on Hypercubes, Spy game: FPT-algorithm and results on graph products, To satisfy impatient web surfers is hard, Cops and robber on subclasses of \(P_5\)-free graphs, A note on the cops and robber game on graphs embedded in non-orientable surfaces, Unnamed Item, Unnamed Item, On the generalised colouring numbers of graphs that exclude a fixed minor, Unnamed Item, On the Conjecture of the Smallest 3-Cop-Win Planar Graph, A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity, Line-of-Sight Pursuit in Monotone and Scallop Polygons, Fine-grained Lower Bounds on Cops and Robbers, Cops and robber on some families of oriented graphs, Bounding the Cop Number of a Graph by Its Genus, Most Generalized Petersen graphs of girth 8 have cop number 4, Fully Active Cops and Robbers, Isometric path numbers of graphs, Finding cut-vertices in the square roots of a graph, Security and Formation of Network-Centric Operations, Chasing robbers on random graphs: Zigzag theorem, Large classes of infinite k-cop-win graphs, Meyniel's conjecture holds for random graphs, Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs, Pursuit evasion on polyhedral surfaces, Vertex Pursuit Games in Stochastic Network Models, On Colourability of Polygon Visibility Graphs, Variations of cops and robbers game on grids, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Model-Free Reinforcement Learning for Stochastic Parity Games, Unnamed Item, Unnamed Item, Control Sequencing in a Game of Identity Pursuit-Evasion, Tandem-win graphs, Conjectures on Cops and Robbers, Cops and Robbers on Graphs Based on Designs, To catch a falling robber, General cops and robbers games with randomness, Cops and robber on butterflies and solid grids, Localization game on geometric and planar graphs, Isometric-path numbers of block graphs, On a pursuit game on Cayley graphs, The capture time of a planar graph, Data center interconnection networks are not hyperbolic, Cops and robbers in graphs with large girth and Cayley graphs, Cooperative pursuit with Voronoi partitions, A deterministic version of the game of zombies and survivors on graphs, The lion and man game on polyhedral surfaces with obstacles, On a pursuit game on Cayley digraphs, On a pursuit game played on graphs for which a minor is excluded, Cops and robbers on intersection graphs, The game of cops and robbers on directed graphs with forbidden subgraphs, A simple method for proving lower bounds in the zero-visibility cops and robber game, A probabilistic version of the game of zombies and survivors on graphs, A faster algorithm for cops and robbers, Catching an infinitely fast robber on a grid, On the cop number of generalized Petersen graphs, A cops and robber game in multidimensional grids, Containment: a variation of cops and robber, Cops and robbers from a distance, Parameterized pursuit-evasion games, The game of overprescribed Cops and Robbers played on graphs, An evasion game on a graph, The guarding game is E-complete, Some remarks on cops and drunk robbers, \(k\)-capture in multiagent pursuit evasion, or the lion and the hyenas, Helicopter search problems, bandwidth and pathwidth, On a characterization of evasion strategies for pursuit-evasion games on graphs, Cop-robber guarding game with cycle robber-region, A simple approach for lower-bounding the distortion in any hyperbolic embedding, Characterizations of \(k\)-copwin graphs, How many ants does it take to find the food?, Visibility graphs, dismantlability, and the cops and robbers game, Almost all cop-win graphs contain a universal vertex, A tight lower bound for the capture time of the cops and robbers game, Cops and robbers on graphs with a set of forbidden induced subgraphs, Cops that surround a robber, On strict (outer-)confluent graphs, On positionality of trigger strategies Nash equilibria in SCAR, The capture time of the hypercube, The one-cop-moves game on graphs with some special structures, The impact of loops on the game of cops and robbers on graphs, Guard games on graphs: keep the intruder out!, How to guard a graph?, Almost all \(k\)-cop-win graphs contain a dominating set of cardinality \(k\), The role of information in the cop-robber game, An annotated bibliography on guaranteed graph searching, Cops and Robbers on diameter two graphs, The pebbling threshold of the square of cliques, \(k\)-chordal graphs: from cops and robber to compact routing via treewidth, Cops and robbers on \(2K_2\)-free graphs, The complexity of pursuit on a graph, The robber locating game, On the cop number of toroidal graphs, Study of a combinatorial game in graphs through linear programming, Spy-game on graphs: complexity and simple topologies, The median game, Escaping offline searchers and isoperimetric theorems, An extension of a fixed point problem for simple graphs, Some pursuit-evasion problems on grids, Lazy Cops and Robbers on generalized hypercubes, The game of Cops and Robber on circulant graphs, Cops and robber game without recharging, Search and sweep numbers of finite directed acyclic graphs, Cops and robbers is EXPTIME-complete, Comparing the power of cops to zombies in pursuit-evasion games, Pursuing a fast robber on a graph, Edge-critical cops and robber in planar graphs, A proof of the Meyniel conjecture for abelian Cayley graphs, Bounds for cops and robber pursuit, A survey on the relationship between the game of cops and robbers and other game representations, Safe navigation in adversarial environments, Throttling for the game of cops and robbers on graphs, Bounds on the length of a game of cops and robbers, 4-cop-win graphs have at least 19 vertices, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Chasing robbers on random geometric graphs-an alternative approach, Cops and robbers on directed and undirected abelian Cayley graphs, The one-cop-moves game on planar graphs, Guarding a subgraph as a tool in pursuit-evasion games, On a game of policemen and robber, Some results about pursuit games on metric spaces obtained through graph theory techniques, An application of the Gyárfás path argument, Product throttling, A two-person game on graphs where each player tries to encircle his opponent's men, Linguistic geometry approach for solving the cops and robber problem in grid environments, Hyperopic cops and robbers, A game of cops and robbers played on products of graphs, A note on cops and robbers, independence number, domination number and diameter, Note on a pursuit game played on graphs, Zero-visibility cops and robber and the pathwidth of a graph, Chasing a drunk robber in many classes of graphs, The optimal capture time of the one-cop-moves game, On a contraction-like property of dismantlable graphs, A short note about pursuit games played on a graph with a given genus, Meyniel extremal families of abelian Cayley graphs
Cites Work
