Scholarlink

This study examines the problem of exploring a random unexplored graph using mobile agents. Starting with n mobile agents at arbitrary nodes in an anonymous graph with n-nodes (G \(=\) V,E) our objective is for the agents to explore the graph while simultaneously forming a subset of nodes S \(\subset \) V that constitutes a MIS(Maximal Independent Set). The MIS guides the exploration, minimizing unnecessary revisits to vertices and maximizing the efficiency of both local and global exploration tasks. We present time-bounded algorithms and simulations for graph exploration by mobile agents by identifying a MIS in different configurations of graphs. These configurations are rooted and dispersed. In the rooted configuration, all mobile agents are initially positioned at a single, designated root node within the network. This setup ensures that the agents begin their exploration from a common starting point, which can simplify coordination and communication among the agents during the exploration process. The root node serves as a central hub, and from there, the agents disperse to explore the rest of the network systematically. In contrast, the dispersed configuration involves distributing the agents uniformly across the network, with each agent initially occupying a distinct and separate node. This configuration allows for a broader initial coverage of the network, enabling agents to simultaneously begin exploring different regions. The dispersed approach can lead to faster exploration times, as there is no need for agents to travel from a single starting point. We evaluated the time complexity for determining MIS by agents possessing 1-hop visibility i.e. each agent can only perceive and gather information about its immediate neighboring nodes within a single hop. The upper bound on time complexity in the 1-hop visibility model, where agents can interact with other agents at a distance of at most 1-hop from their location, for rooted configuration is given by O(n). The time complexity of finding the MIS in the dispersed configuration, characterized by the placement of at most a single agent per node, is bounded by \(O(1)\) .

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Graph Exploration Using Mobile Agents

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Sushant Bakshi,
  • Rishi Srivastava,
  • Arka Ghosh,
  • Sayandeb Sarkar,
  • Sruti Gan Chaudhuri

摘要

This study examines the problem of exploring a random unexplored graph using mobile agents. Starting with n mobile agents at arbitrary nodes in an anonymous graph with n-nodes (G \(=\) V,E) our objective is for the agents to explore the graph while simultaneously forming a subset of nodes S \(\subset \) V that constitutes a MIS(Maximal Independent Set). The MIS guides the exploration, minimizing unnecessary revisits to vertices and maximizing the efficiency of both local and global exploration tasks. We present time-bounded algorithms and simulations for graph exploration by mobile agents by identifying a MIS in different configurations of graphs. These configurations are rooted and dispersed. In the rooted configuration, all mobile agents are initially positioned at a single, designated root node within the network. This setup ensures that the agents begin their exploration from a common starting point, which can simplify coordination and communication among the agents during the exploration process. The root node serves as a central hub, and from there, the agents disperse to explore the rest of the network systematically. In contrast, the dispersed configuration involves distributing the agents uniformly across the network, with each agent initially occupying a distinct and separate node. This configuration allows for a broader initial coverage of the network, enabling agents to simultaneously begin exploring different regions. The dispersed approach can lead to faster exploration times, as there is no need for agents to travel from a single starting point. We evaluated the time complexity for determining MIS by agents possessing 1-hop visibility i.e. each agent can only perceive and gather information about its immediate neighboring nodes within a single hop. The upper bound on time complexity in the 1-hop visibility model, where agents can interact with other agents at a distance of at most 1-hop from their location, for rooted configuration is given by O(n). The time complexity of finding the MIS in the dispersed configuration, characterized by the placement of at most a single agent per node, is bounded by \(O(1)\) .