EUVIMEDEUVIMED entdecken
Crossref

The one-visibility localization game

Anthony Bonato, Trent G. Marbach, Michael Molnar, JD Nir

Theoretical Computer Science · 2023-11 · 978 · 114186

DOI: 10.1016/j.tcs.2023.114186 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Theoretical Computer Science, 2023-11. Verfasst von Anthony Bonato und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We introduce a variant of the Localization game in which the cops only have visibility one, along with the corresponding optimization parameter, the one-visibility localization number $\zeta_1$. By developing lower bounds using isoperimetric inequalities, we give upper and lower bounds for $\zeta_1$ on $k$-ary trees with $k\ge 2$ that differ by a multiplicative constant, showing that the parameter is unbounded on $k$-ary trees. We provide a $O(\sqrt{n})$ bound for $K_h$-minor free graphs of order $n$, and we show Cartesian grids meet this bound by determining their one-visibility localization number up to four values. We present upper bounds on $\zeta_1$ using pathwidth and the domination number and give upper bounds on trees via their depth and order. We conclude with open problems.

Förderung

  • Natural Sciences and Engineering Research Council of Canada

Zitieren

APA

Bonato, A., Marbach, T. G., Molnar, M., & Nir, J. (2023). The one-visibility localization game. Theoretical Computer Science, 978, 114186. https://doi.org/10.1016/j.tcs.2023.114186

Vancouver

Bonato A, Marbach TG, Molnar M, Nir J. The one-visibility localization game. Theoretical Computer Science. 2023;978:114186. doi:10.1016/j.tcs.2023.114186

BibTeX
@article{Bonato2023,
  author = {Bonato, Anthony and Marbach, Trent G. and Molnar, Michael and Nir, JD},
  title = {The one-visibility localization game},
  journal = {Theoretical Computer Science},
  year = {2023},
  volume = {978},
  pages = {114186},
  doi = {10.1016/j.tcs.2023.114186}
}
Kostenlos starten →