Document Open Access Logo

Faster Exploration of Some Temporal Graphs

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

PDF
Thumbnail PDF

File

LIPIcs.SAND.2022.5.pdf
  • Filesize: 0.59 MB
  • 10 pages

Document Identifiers

Author Details

Duncan Adamson
  • Department of Computer Science, Reykjavik University, Iceland
Vladimir V. Gusev
  • Materials Innovation Factory, University of Liverpool, UK
  • Department of Computer Science, University of Liverpool
Dmitriy Malyshev
  • Laboratory of Algorithms and Technologies for Network Analysis, HSE University, Nizhny Novgorod, Russian Federation
Viktor Zamaraev
  • Department of Computer Science, University of Liverpool, UK

Funding

  • Adamson, Duncan: Funded by the Leverhulme trust.
  • Gusev, Vladimir V.: funded by the Leverhulme trust.
  • Malyshev, Dmitriy: The work of Dmitriy Malyshev was conducted within the framework of the Basic Research Program at the National Research University Higher School of Economics (HSE).

Cite AsGet BibTex

Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SAND.2022.5

Abstract

A temporal graph G = (G_1, G_2, ..., G_T) is a graph represented by a sequence of T graphs over a common set of vertices, such that at the i-th time step only the edge set E_i 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(k n^{1.5} log n) days if the underlying graph has treewidth k and in O(n^{1.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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Temporal Graphs
  • Graph Exploration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Eleni C Akrida, George B Mertzios, Paul G Spirakis, and Christoforos Raptopoulos. The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120:179-193, 2021. Google Scholar
  2. Hans L Bodlaender and Tom C van der Zanden. On exploring always-connected temporal graphs of small pathwidth. Information Processing Letters, 142:68-71, 2019. Google Scholar
  3. Thomas Erlebach, Michael Hoffmann, and Michael Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1-18, 2021. Google Scholar
  4. Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T Spooner. Two moves per time step make a difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  5. Thomas Erlebach and Jakob T. Spooner. Exploration of k-edge-deficient temporal graphs. In Anna Lubiw and Mohammad Salavatipour, editors, Algorithms and Data Structures, pages 371-384, Cham, 2021. Springer International Publishing. Google Scholar
  6. Greg Frederickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal of Computing, 16:1004-1022, 1987. Google Scholar
  7. Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1-23, 2016. Google Scholar
  8. Shadi Taghian Alamouti. Exploring temporal cycles and grids. Master’s thesis, Concordia University, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact