An optimal algorithm for geodesic mutual visibility on hexagonal grids

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 \tex...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-05
Main Authors: Badri, Sahar, Cicerone, Serafino, Alessia Di Fonso, Gabriele Di Stefano
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Combinatorial analysis
Graph theory
Messages
Optimization
Robots
Shortest-path problems
Visibility
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \textsc{Geodesic Mutual Visibility} (GMV, for short) 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 \(G_k\). This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in \(G_k\).
ISSN:2331-8422