Faster exploration of some temporal graphs

Duncan Adamson*, Vladimir V. Gusev*, Dmitriy Malyshev*, Viktor Zamaraev*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022
EditorsJames Aspnes, Othon Michail
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772242
DOIs
Publication statusPublished - 29 Apr 2022
Event1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022 - Virtual, Online
Duration: 28 Mar 202230 Mar 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume221
ISSN (Print)1868-8969

Conference

Conference1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022
CityVirtual, Online
Period28/03/2230/03/22

Keywords

  • Graph Exploration
  • Temporal Graphs

Fingerprint

Dive into the research topics of 'Faster exploration of some temporal graphs'. Together they form a unique fingerprint.

Cite this