Self-stabilizing Graph Exploration by a Single Agent
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915238271516672 |
|---|---|
| author | Sudo, Yuichi Ooshita, Fukuhito Kamei, Sayaka |
| author_facet | Sudo, Yuichi Ooshita, Fukuhito Kamei, Sayaka |
| contents | In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. Starting from any initial configuration, \ie regardless of the initial states of the agent and all nodes, as well as the initial location of the agent, the algorithms ensure the agent visits all nodes. We evaluate the algorithms based on two metrics: the \emph{cover time}, defined as the number of moves required to visit all nodes, and \emph{memory usage}, defined as the storage needed for maintaining the states of the agent and each node. The first algorithm is randomized. Given an integer $c = Ω(n)$, its cover time is optimal, \ie $O(m)$ in expectation, and its memory requirements are $O(\log c)$ bits for the agent and $O(\log (c+δ_v))$ bits for each node $v$, where $n$ and $m$ are the numbers of nodes and edges, respectively, and $δ_v$ is the degree of node $v$. For general $c \ge 2$, its cover time is $O( m \cdot \min(D, \frac{n}{c}+1, \frac{D}{c} + \log n))$, where $D$ is the diameter of a graph. The second algorithm is deterministic. It requires an input integer $k \ge \max(D, \dmax)$, where $\dmax$ is the maximum degree of the graph. The cover time of this algorithm is $O(m + nD)$, and it uses $O(\log k)$ bits of memory for both the agent and each node. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2010_08929 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Self-stabilizing Graph Exploration by a Single Agent Sudo, Yuichi Ooshita, Fukuhito Kamei, Sayaka Distributed, Parallel, and Cluster Computing In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. Starting from any initial configuration, \ie regardless of the initial states of the agent and all nodes, as well as the initial location of the agent, the algorithms ensure the agent visits all nodes. We evaluate the algorithms based on two metrics: the \emph{cover time}, defined as the number of moves required to visit all nodes, and \emph{memory usage}, defined as the storage needed for maintaining the states of the agent and each node. The first algorithm is randomized. Given an integer $c = Ω(n)$, its cover time is optimal, \ie $O(m)$ in expectation, and its memory requirements are $O(\log c)$ bits for the agent and $O(\log (c+δ_v))$ bits for each node $v$, where $n$ and $m$ are the numbers of nodes and edges, respectively, and $δ_v$ is the degree of node $v$. For general $c \ge 2$, its cover time is $O( m \cdot \min(D, \frac{n}{c}+1, \frac{D}{c} + \log n))$, where $D$ is the diameter of a graph. The second algorithm is deterministic. It requires an input integer $k \ge \max(D, \dmax)$, where $\dmax$ is the maximum degree of the graph. The cover time of this algorithm is $O(m + nD)$, and it uses $O(\log k)$ bits of memory for both the agent and each node. |
| title | Self-stabilizing Graph Exploration by a Single Agent |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2010.08929 |