Search Results

Documents authored by Sanlaville, Eric

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
DOI: 10.4230/LIPIcs.SAND.2024.8
On Inefficiently Connecting Temporal Networks

Authors: Esteban Christiann, Eric Sanlaville, and Jason Schoeters

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

Abstract
A temporal graph can be represented by a graph with an edge labelling, such that an edge is present in the network if and only if the edge is assigned the corresponding time label. A journey is a labelled path in a temporal graph such that labels on successive edges of the path are increasing, and if all vertices admit journeys to all other vertices, the temporal graph is temporally connected. A temporal spanner is a sublabelling of the temporal graph such that temporal connectivity is maintained. The study of temporal spanners has raised interest since the early 2000’s. Essentially two types of studies have been conducted: the positive side where families of temporal graphs are shown to (deterministically or stochastically) admit sparse temporal spanners, and the negative side where constructions of temporal graphs with no sparse spanners are of importance. Often such studies considered temporal graphs with happy or simple labellings, which associate exactly one label per edge. In this paper, we focus on the negative side and consider proper labellings, where multiple labels per edge are allowed. More precisely, we aim to construct dense temporally connected graphs such that all labels are necessary for temporal connectivity. Our contributions are multiple: we present exact or asymptotically tight results for basic graph families, which are then extended to larger graph families; an extension of an efficient temporal graph labelling generator; and overall denser labellings than previous work, whether it be global or local density.
Cite as

Esteban Christiann, Eric Sanlaville, and Jason Schoeters. On Inefficiently Connecting Temporal Networks. In 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 292, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{christiann_et_al:LIPIcs.SAND.2024.8,
  author =	{Christiann, Esteban and Sanlaville, Eric and Schoeters, Jason},
  title =	{{On Inefficiently Connecting Temporal Networks}},
  booktitle =	{3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)},
  pages =	{8:1--8:19},
  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.8},
  URN =		{urn:nbn:de:0030-drops-198867},
  doi =		{10.4230/LIPIcs.SAND.2024.8},
  annote =	{Keywords: Network design principles, Network dynamics, Paths and connectivity problems, Branch-and-bound}
}
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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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