1 Search Results for "Malyshev, Dmitriy"

Document
DOI: 10.4230/LIPIcs.SAND.2022.5
Faster Exploration of Some Temporal Graphs

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

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{adamson_et_al:LIPIcs.SAND.2022.5,
  author =	{Adamson, Duncan and Gusev, Vladimir V. and Malyshev, Dmitriy and Zamaraev, Viktor},
  title =	{{Faster Exploration of Some Temporal Graphs}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.5},
  URN =		{urn:nbn:de:0030-drops-159475},
  doi =		{10.4230/LIPIcs.SAND.2022.5},
  annote =	{Keywords: Temporal Graphs, Graph Exploration}
}
  • Refine by Author
  • 1 Adamson, Duncan
  • 1 Gusev, Vladimir V.
  • 1 Malyshev, Dmitriy
  • 1 Zamaraev, Viktor

  • Refine by Classification
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 1 Graph Exploration
  • 1 Temporal Graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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