Title: Minimizing the Cost of Team Exploration,
Abstract: A group of mobile agents is given a task to explore an edge-weighted graph
$G$, i.e., every vertex of $G$ has to be visited by at least one agent. There
is no centralized unit to coordinate their actions, but they can freely
communicate with each other. The goal is to construct a deterministic strategy
which allows agents to complete their task optimally. In this paper we are
interested in a cost-optimal strategy, where the cost is understood as the
total distance traversed by agents coupled with the cost of invoking them. Two
graph classes are analyzed, rings and trees, in the off-line and on-line
setting, i.e., when a structure of a graph is known and not known to agents in
advance. We present algorithms that compute the optimal solutions for a given
ring and tree of order $n$, in $O(n)$ time units. For rings in the on-line
setting, we give the $2$-competitive algorithm and prove the lower bound of
$3/2$ for the competitive ratio for any on-line strategy. For every strategy
for trees in the on-line setting, we prove the competitive ratio to be no less
than $2$, which can be achieved by the $DFS$ algorithm.