Adamson, D 
ORCID: 0000-0003-3343-2435, Gusev, VV, Malyshev, D and Zamaraev, V ORCID: 0000-0001-5755-4141
(2022)
Faster Exploration of Some Temporal Graphs.
.
|
Text
main.pdf - Author Accepted Manuscript Download (353kB) | Preview |
Abstract
A temporal graph G = (G1, G2,..., GT ) is a graph represented by a sequence of T graphs over a common set of vertices, such that at the ith time step only the edge set Ei is active. The temporal graph exploration problem asks for a shortest temporal walk on some temporal graph visiting every vertex. We show that temporal graphs with n vertices can be explored in O(kn1.5 log n) days if the underlying graph has treewidth k and in O(n1.75 log n) days if the underlying graph is planar. Furthermore, we show that any temporal graph whose underlying graph is a cycle with k chords can be explored in at most 6kn days. Finally, we demonstrate that there are temporal realisations of sub cubic planar graphs that cannot be explored faster than in Ω(n log n) days. All these improve best known results in the literature.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 13 Jun 2022 13:56 |
| Last Modified: | 27 Nov 2023 21:05 |
| DOI: | 10.4230/LIPIcs.SAND.2022.5 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3156375 |
Dimensions
Dimensions
