Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Localization game for random geometric graphs
Indexado
WoS WOS:000888539000004
Scopus SCOPUS_ID:85140085691
DOI 10.1016/J.EJC.2022.103616
Año 2023
Tipo artículo de investigación

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



The localization game is a two player combinatorial game played on a graph G = (V, E). The cops choose a set of vertices S1 subset of V with |S1| = k. The robber then chooses a vertex v is an element of V whose location is hidden from the cops, but the cops learn the graph distance between the current position of the robber and the vertices in S1. If this information is sufficient to locate the robber, the cops win immediately; otherwise the cops choose another set of vertices S2 subset of V with |S2| = k, and the robber may move to a neighboring vertex. The new distances to the robber are presented, and if the cops can deduce the new location of the robber based on all information they accumulated thus far, then they win; otherwise, a new round begins. If the robber has a strategy to avoid being captured, then she wins. The localization number is defined to be the smallest integer k so that the cops win the game. In this paper we determine the localization number (up to poly-logarithmic factors) of the random geometric graph G is an element of G(n, r) slightly above the connectivity threshold.(c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Mathematics
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Lichev, Lyuben Hombre Univ Jean Monnet - Francia
Université Jean Monnet Saint Etienne - Francia
2 Mitsche, Dieter Hombre Univ Jean Monnet - Francia
Pontificia Universidad Católica de Chile - Chile
Université Jean Monnet Saint Etienne - Francia
3 Pralat, Pawel Hombre Toronto Metropolitan Univ - Canadá
Toronto Metropolitan University - Canadá

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Fondo Nacional de Desarrollo Científico y Tecnológico

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Dieter Mitsche has been partially supported by Fondecyt, Chile grant 1220174 and by grant GrHyDy, FranceANR-20-CE40-0002.

Muestra la fuente de financiamiento declarada en la publicación.