The localization capture time of a graph

Natalie Behague, Anthony Bonato, Melissa A. Huggan, Trent G. Marbach, Brittany Pittman · Theoretical Computer Science · 2021

Explore this paper's citation graph

Summary

A novel graph parameter called the capture time is presented, which measures how long the localization game lasts assuming optimal play, and conjecture that the captureTime is linear in the order of the graph, and shows that the conjecture holds for graph families such as trees and interval graphs.

Type: preprint
Published: 2021-05-20
Cited by: 9
References: 31
Access: Open access
DOI: https://doi.org/10.1016/j.tcs.2022.02.007
arXiv: https://arxiv.org/abs/2105.09806
OpenAlex: https://openalex.org/W3161320300
Semantic Scholar: https://api.semanticscholar.org/CorpusID:234789978

Keywords

Treewidth, Combinatorics, Monotone polygon, Conjecture, Time complexity

References

Combinatorics: Topics, Techniques, AlgorithmsRobert L. Patten — 1995
Graph Searching and Related ProblemsAnthony Bonato, Boting Yang — 2013
The Game of Cops and Robbers on GraphsAnthony Bonato, Richard J. Nowakowski — 2011
Graph Classes: A SurveyAndreas Brandstädt, Van Bang Lê, Jeremy Spinrad — 1987
Locating a backtracking robber on a treeSuzanne M. Seager — 2014
Locating a robber on a graphSuzanne M. Seager — 2012
On the Cop Number of a GraphAlessandro Berarducci, Benedetto Intrigila — 1993
Recontamination does not help to search a graphAndrea S. LaPaugh — 1993
Monotonicity in Graph SearchingDaniel Bienstock, Paul Seymour — 1991
Graph Searching and a Min-Max Theorem for Tree-WidthPaul Seymour, Rajan M. Thomas — 1993
The capture time of a graphAnthony Bonato, Petr A. Golovach, G. Hahn — 2009
Locating a robber on a graph via distance queriesJames M. Carraher, Ilkyoo Choi, Michelle Delcourt — 2012
An annotated bibliography on guaranteed graph searchingFedor V. Fomin, Dimitrios M. Thilikos — 2008
The Game of Overprescribed Cops and Robbers Played on GraphsAnthony Bonato, Xavier Pérez‐Giménez, Paweł Prałat — 2016
Bounds on the length of a game of Cops and RobbersWilliam B. Kinnersley — 2017
A Tight Lower Bound for the Capture Time of the Cops and Robbers GameSebastian Brandt, Yuval Emek, Jara Uitto — 2020
Locating a robber with multiple probesJohn Haslegrave, Richard A. B. Johnson, Sebastian Koch — 2017
A robber locating strategy for treesAxel Brandt, Jennifer Diemunsch, Catherine Erbes — 2017
Localization game on geometric and planar graphsBartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk — 2017
Centroidal localization gameBartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk — 2017

Cited by

The localization game on oriented graphsAnthony Bonato, Ryan Cushman, Trent G. Marbach — 2023
Locating Robber with Cop Strategy Graph: Subdivision vs. Multiple CopShiqi Pan — 2023
The one-visibility Localization gameAnthony Bonato, Trent G. Marbach, Michael Molnar — 2023
Localization game capture time of trees and outerplanar graphsChenoweth, Vesna Iršič, Skrt, Matija — 2025
A note on robber locating gameRahul Das, Ushnish Sarkar — 2026
The k-visibility Localization GameAnthony Bonato, Trent G. Marbach, John Marcoux — 2023
Locally finite graphs and their localization numbersAnthony Bonato, Florian Lehner, Trent G. Marbach — 2024
Edge and Pair Queries - Random Graphs and ComplexityDariusz Dereniowski, Przemysław Gordinowicz, Paweł Prałat — 2022
The Localization Game on Directed GraphsAnthony Bonato, Ryan Cushman, Trent G. Marbach — 2022

The localization capture time of a graph

Summary

Keywords

References

Cited by

Related papers