View article

In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporal graphs. A temporal graph D=(V, A) may be viewed as a time-sequence G 1, G 2,…, G l of static graphs over the same (static) set of nodes V. Each G t= D (t)=(V, A (t)) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of traveling salesman problems in temporal graphs. A sequence of time-labeled edges (eg a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c> 0, in a special case of temporal graphs and within (2− ε), for every constant ε> 0, in another special case in which D (t) is …