DROPS

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

Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management

DOI: 10.4230/LIPIcs.ICALP.2019.134

Temporal Cliques Admit Sparse Spanners

Authors: Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract

Let G=(V,E) be an undirected graph on n vertices and lambda:E -> 2^{N} a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph {G}=(G,lambda) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (STOC 2000) asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity - a temporal spanner. Axiotis and Fotakis (ICALP 2016) answered negatively by exhibiting a family of Theta(n^2)-dense temporal graphs which admit no temporal spanner of density o(n^2). The natural question is then whether sparse temporal spanners always exist in some classes of dense graphs. In this paper, we answer this question affirmatively, by showing that if the underlying graph G is a complete graph, then one can always find temporal spanners of density O(n log n). The best known result for complete graphs so far was that spanners of density binom{n}{2}- floor[n/4] = O(n^2) always exist. Our result is the first positive answer as to the existence of o(n^2) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al., focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.

Cite as

Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal Cliques Admit Sparse Spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 134:1-134:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.ICALP.2019.134,
  author =	{Casteigts, Arnaud and Peters, Joseph G. and Schoeters, Jason},
  title =	{{Temporal Cliques Admit Sparse Spanners}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{134:1--134:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.134},
  URN =		{urn:nbn:de:0030-drops-107108},
  doi =		{10.4230/LIPIcs.ICALP.2019.134},
  annote =	{Keywords: Dynamic networks, Temporal graphs, Temporal connectivity, Sparse spanners}
}

Search Results

Documents authored by Schoeters, Jason

On Inefficiently Connecting Temporal Networks

Abstract

Cite as

Temporal Cliques Admit Sparse Spanners

Abstract

Cite as

Thanks for your feedback!

Could not send message