Abstract
In this paper, we study collision-free graph exploration in an anonymous network. The network is modeled as a graph G = (V, E) where the nodes of the graph are unlabeled, and each edge incident to a node v has a unique label, called the port number, in {0, 1, ⋯, d - 1}, where d is the degree of the node v. Two identical mobile agents, starting from different nodes in G have to explore the nodes of G in such a way that for every node v in G, at least one mobile agent visits v and no two agents are in the same node in any round and stop. The time of exploration is the minimum round number by which both agents have terminated. The agents know the size of the graph but do not know its topology. If an agent arrives in the one-hop neighborhood of the other agent, both agents can detect the presence of the other agent but have no idea at which neighboring node the other agent resides. The agents may wake up in different rounds, but once awake, they execute a deterministic algorithm in synchronous rounds. An agent, after waking up, has no knowledge about the wake-up time of the other agent. The task of collision-free exploration is impossible to solve even for a line of length 2 where the agents are placed at the end nodes of the line and even if both agents wake up at the same time. We study the problem of collision-free exploration where some pebbles are placed by an Oracle at the nodes of the graph to assist the agents in achieving collision-free exploration. The Oracle knows the graph, the starting positions of the agents, and their wake-up schedule, and it places some pebbles that may be of different colors, at most one at each node. The number of different colors of the pebbles placed by the Oracle is called the color index of the corresponding pebble placement algorithm. The central question we study in this paper is: "What is the minimum number z such that there exists a collision-free exploration of a given graph with pebble placement of color index z?". For general graphs, we show that it is impossible to design a deterministic algorithm that achieves collision-free exploration with color index 1. We propose an exploration algorithm with color index 3. We also proposed a polynomial exploration algorithm for bipartite graphs with color index 2.
Recommended Citation
S. K. Das et al., "Collision-free Exploration by Mobile Agents Using Pebbles," ICDCN 2025 - Proceedings of the 26th International Conference on Distributed Computing and Networking, pp. 161 - 170, Association for Computing Machinery, Jan 2025.
The definitive version is available at https://doi.org/10.1145/3700838.3700863
Department(s)
Computer Science
Publication Status
Open Access
Keywords and Phrases
Anonymous graph; Deterministic Algorithms; Exploration; Mobile agent
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2025 Association for Computing Machinery, All rights reserved.
Creative Commons Licensing
This work is licensed under a Creative Commons Attribution 4.0 License.
Publication Date
04 Jan 2025
Comments
Science and Engineering Research Board, Grant MTR/2021/000118