For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through shortest paths). These properties can be obtained if the Geodesic Mutual Visibility (GMV) problem is solved: oblivious robots move along the edges of the graph, without collisions, to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. In this work, we optimally solve GMV on finite hexagonal grids Gk. This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in Gk.

An Optimal Algorithm for Geodesic Mutual Visibility on Hexagonal Grids

Badri S.;Cicerone S.;Di Fonso A.;Di Stefano G.
2025-01-01

Abstract

For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through shortest paths). These properties can be obtained if the Geodesic Mutual Visibility (GMV) problem is solved: oblivious robots move along the edges of the graph, without collisions, to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. In this work, we optimally solve GMV on finite hexagonal grids Gk. This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in Gk.
2025
9783031744976
9783031744983
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/246643
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact