Graph Searching and Related Problems

Keywords

Graph, Null graph, Probabilistic logic, Combinatorics, Computer science

References

• A course on the Web graphAnthony Bonato — 2008
• Random Graphs: Second EditionBéla Bollobás — 2001
• TreewidthTon Kloks — 1994
• A Cover-Based Approach to Multi-Agent Moving Target PursuitAlejandro Isaza, Jieshan Lu, Vadim Bulitko — 2008
• The Game of Cops and Robbers on GraphsAnthony Bonato, Richard J. Nowakowski — 2011
• Random Graphs: NotationBéla Bollobás — 2001
• The Mathematics of Paul Erdős IIRonald Graham, Jaroslav Nešetřil, Steve Butler — 1997
• On Meyniel's conjecture of the cop numberLinyuan Lü, Xing Peng — 2012
• SEARCHING AND SWEEPING GRAPHS: A BRIEF SURVEYBrian Alspach — 2006
• Evaluating Strategies for Running from the CopsCarsten Moldenhauer, Nathan Sturtevant — 2009
• The Cops & Robber game on series-parallel graphsDirk Oliver Theis — 2007
• Variations on cops and robbersAlan Frieze, Michael Krivelevich, Po‐Shen Loh — 2010
• On the Complexity of the Balanced Vertex Ordering ProblemJan Kára, Jan Kratochvı́l, David R. Wood — 2005
• Optimal Algorithms for a Pursuit-Evasion Problem in GridsKazuo Sugihara, I. Suzuki — 1989
• Classes of pebble games and complete problemsT. Kasai, Akeo Adachi, Shigeki Iwata — 1979
• Directed Path-width and Monotonicity in Digraph SearchingJános Barát — 2006
• A family of countable homogeneous graphsC. Ward Henson — 1971
• Cops and Robbers from a distanceAnthony Bonato, Ehsan Chiniforooshan, Paweł Prałat — 2010
• Digraph measures: Kelly decompositions, games, and orderingsPaul Hunter, Stephan Kreutzer — 2007
• On the evolution of random graphsBéla Bollobás — 1984

Cited by

• The optimal capture time of the one-cop-moves gameBoting Yang, William Hamilton — 2015
• The fast robber on interval and chordal graphsAbbas Mehrabian — 2015
• Cops-and-robbers: Remarks and problemsM. Martin Boyer, S. Harti, A. Ouarari — 2013
• The role of quantum correlations in Cop and Robber gameAdam Glos, Jarosław Adam Miszczak — 2017
• Algorithmic complexity: Between Structure and Knowledge How Pursuit-evasion Games help. (Complexité algorithmique: entre structure et connaissance. Comment les jeux de poursuite peuvent apporter des solutions)Nicolas Nisse — 2014
• The fast search number of a Cartesian product of graphsYuan Xue, Boting Yang — 2017
• A Tight Lower Bound for the Capture Time of the Cops and Robbers GameSebastian Brandt, Yuval Emek, Jara Uitto — 2020
• Hyperopic Cops and RobbersAnthony Bonato, Nancy E. Clarke, Danielle Cox — 2017
• Bounds on the localization numberAnthony Bonato, William B. Kinnersley — 2018
• Equivalence between Linear Tangle and Maximal Single IdealTakaaki Fujita, Koichi Yamazaki — 2019
• A Sublinear Bound on the Cop Throttling Number of a GraphAnthony Bonato, Sean English — 2019
• Guarding a Subgraph as a Tool in Pursuit-Evasion GamesDrago Bokal, Janja Jerebic — 2021
• The Chinese deliveryman problemMartijn van Ee, René Sitters — 2019
• The localization number of designsAnthony Bonato, Melissa A. Huggan, Trent G. Marbach — 2020
• The localization number and metric dimension of graphs of diameter 2Anthony Bonato, Melissa A. Huggan, Trent G. Marbach — 2020
• The one-cop-moves game on graphs with some special structuresLusheng Wang, Boting Yang — 2020
• Lower Bounds and Algorithms for Searching NetworksYuan Xue — 2019
• A simple method for proving lower bounds in the zero-visibility cops and robber gameYuan Xue, Boting Yang, Sandra Zilles — 2021
• Searching for an Intruder on Graphs and Their SubdivisionsAnton Bernshteyn, Eugene Lee — 2021
• The localization capture time of a graphNatalie Behague, Anthony Bonato, Melissa A. Huggan — 2021

Related papers

• The Game of Cops and Robbers on GraphsAnthony Bonato, Richard J. Nowakowski — 2011
• Vertex-to-vertex pursuit in a graphRichard J. Nowakowski, Peter Winkler — 1983
• An annotated bibliography on guaranteed graph searchingFedor V. Fomin, Dimitrios M. Thilikos — 2008
• A game of cops and robbersMartin Aigner, M. Fromme — 1984
• Cops and robbers in graphs with large girth and Cayley graphsPéter Frankl — 1987
• On Meyniel's conjecture of the cop numberLinyuan Lü, Xing Peng — 2012
• Cops and Robbers is EXPTIME-completeWilliam B. Kinnersley — 2013
• The capture time of a graphAnthony Bonato, Petr A. Golovach, G. Hahn — 2009