In a connected graph with an autonomous robot swarm with limited visibility, it is natural to ask whether the robots can be deployed to certain vertices satisfying a given property using only local knowledge. This paper affirmatively answers the question with a set of myopic (finite visibility range) luminous robots with the aim of filling a minimal vertex cover (MVC) of a given graph \(G = (V, E)\) . The graph has special vertices, called doors, through which robots enter sequentially. Starting from the doors, the goal of the robots is to settle on a set of vertices that forms a minimal vertex cover of G under the asynchronous ( \(\mathcal {ASYNC}\) ) scheduler. We are also interested in achieving the minimum vertex cover (MinVC, which is NP-hard [14] for general graphs) for a specific graph class using the myopic robots. We establish lower bounds on the visibility range for the robots and on the time complexity (which is \(\varOmega (|E|)\) ). We present two algorithms for trees: one for single door, which is both time and memory-optimal, and the other for multiple doors, which is memory-optimal and achieves time-optimality when the number of doors is a constant. Interestingly, our technique achieves MinVC on trees with a single door. We then move to the general graph, where we present two algorithms, one for the single door and the other for the multiple doors with an extra memory of \(O(\log \varDelta )\) for the robots, where \(\varDelta \) is the maximum degree of G. All our algorithms run in O(|E|) epochs.

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

Time-Optimal Asynchronous Minimal Vertex Covering by Myopic Robots on Graph

  • Saswata Jana,
  • Subhajit Pramanick,
  • Adri Bhattacharya,
  • Partha Sarathi Mandal

摘要

In a connected graph with an autonomous robot swarm with limited visibility, it is natural to ask whether the robots can be deployed to certain vertices satisfying a given property using only local knowledge. This paper affirmatively answers the question with a set of myopic (finite visibility range) luminous robots with the aim of filling a minimal vertex cover (MVC) of a given graph \(G = (V, E)\) . The graph has special vertices, called doors, through which robots enter sequentially. Starting from the doors, the goal of the robots is to settle on a set of vertices that forms a minimal vertex cover of G under the asynchronous ( \(\mathcal {ASYNC}\) ) scheduler. We are also interested in achieving the minimum vertex cover (MinVC, which is NP-hard [14] for general graphs) for a specific graph class using the myopic robots. We establish lower bounds on the visibility range for the robots and on the time complexity (which is \(\varOmega (|E|)\) ). We present two algorithms for trees: one for single door, which is both time and memory-optimal, and the other for multiple doors, which is memory-optimal and achieves time-optimality when the number of doors is a constant. Interestingly, our technique achieves MinVC on trees with a single door. We then move to the general graph, where we present two algorithms, one for the single door and the other for the multiple doors with an extra memory of \(O(\log \varDelta )\) for the robots, where \(\varDelta \) is the maximum degree of G. All our algorithms run in O(|E|) epochs.