Back to Search
Start Over
On temporal graph exploration.
- Source :
-
Journal of Computer & System Sciences . Aug2021, Vol. 119, p1-18. 18p. - Publication Year :
- 2021
-
Abstract
- The temporal graph exploration problem TEXP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. In the first and second part of the paper, we consider only undirected temporal graphs that are connected at each time step. For such temporal graphs with n nodes, we show that it is NP -hard to approximate TEXP with ratio O (n 1 − ε) for every ε > 0 and present several solutions for special graph classes. In the third part of the paper, we consider settings where the graphs in future time steps are not known. We show that m -edge temporal graphs with regularly present edges and with probabilistically present edges can be explored online in O (m) time steps and O (m log n) time steps with high probability, respectively. [ABSTRACT FROM AUTHOR]
- Subjects :
- *UNDIRECTED graphs
*PLANAR graphs
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 119
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 149495107
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.01.005