DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2025.18

Brief Announcement: The Shortest Temporal Exploration Problem

Authors: Stefan Balev, Éric Sanlaville, and Antoine Toullalan

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract

A temporal graph is a graph for which the edge set can change from one time step to the next. This paper considers undirected temporal graphs defined over L time steps and connected at each time step. We study the Shortest Temporal Exploration Problem (STEXP) that, given the evolution of the graph, asks for a temporal walk that starts at a given vertex, moves over at most one edge at each time step, visits all the vertices, takes at most L time steps and traverses the smallest number of edges. We prove that every constantly connected temporal graph with n vertices can be explored with O(n^{1.5}) edges traversed if L is O(n^{3.5}) time steps. This result improves the upper bound of O(n²) edges when L is Ω(n²). Moreover, we study the case where the graph has a diameter bounded by a parameter k at each time step and we prove that there exists an exploration which takes O(kn²) time steps and traverses O(kn) edges. Finally, the case where the underlying graph is a cycle is studied and tight linear bounds are provided on the number of edges traversed in the worst-case.

Cite as

Stefan Balev, Éric Sanlaville, and Antoine Toullalan. Brief Announcement: The Shortest Temporal Exploration Problem. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 18:1-18:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balev_et_al:LIPIcs.SAND.2025.18,
  author =	{Balev, Stefan and Sanlaville, \'{E}ric and Toullalan, Antoine},
  title =	{{Brief Announcement: The Shortest Temporal Exploration Problem}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{18:1--18:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.18},
  URN =		{urn:nbn:de:0030-drops-230716},
  doi =		{10.4230/LIPIcs.SAND.2025.18},
  annote =	{Keywords: Graph Theory, Temporal Graph, Temporal Graph Exploration}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.SAND.2024.24

Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms

Authors: Stefan Balev, Yoann Pigné, Éric Sanlaville, and Mathilde Vernet

Published in: LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)

Abstract

This note introduces an extension of the Steiner tree problem applied to dynamic graphs. It discusses its interest, studies its complexity and proposes an algorithm tested on generated and real data.

Cite as

Stefan Balev, Yoann Pigné, Éric Sanlaville, and Mathilde Vernet. Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 24:1-24:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balev_et_al:LIPIcs.SAND.2024.24,
  author =	{Balev, Stefan and Pign\'{e}, Yoann and Sanlaville, \'{E}ric and Vernet, Mathilde},
  title =	{{Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{24:1--24:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-315-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{292},
  editor =	{Casteigts, Arnaud and Kuhn, Fabian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.24},
  URN =		{urn:nbn:de:0030-drops-199026},
  doi =		{10.4230/LIPIcs.SAND.2024.24},
  annote =	{Keywords: Steiner Tree, Dynamic Graph, Complexity, experimental study}
}

Search Results

Documents authored by Balev, Stefan

Brief Announcement: The Shortest Temporal Exploration Problem

Abstract

Cite as

Brief Announcement: The Dynamic Steiner Tree Problem: Definitions, Complexity, Algorithms

Abstract

Cite as

Thanks for your feedback!

Could not send message