Algorithmics and Computational Complexity Research GroupTalk 113.06.2019

# Finding and Exploiting Structure in Highly-Dynamic Networks

Arnaud Casteigts (University of Bordeaux)



Let G=(V,E) be an undirected graph on n vertices and λ:E→2N 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,λ) 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 (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 (2016) answered negatively by exhibiting a family of Θ(n2)-dense temporal graphs which admit no temporal spanner of density o(n2). The natural question is then whether sparse temporal spanners can always be found 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 (n2)−⌊n/4⌋=O(n2) always exist. Our result is the first positive answer as to the existence of o(n2) 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.

(joint work with Joseph Peters and Jason Schoeters, to appear in ICALP 2019)

Date
Speaker
Location
Language
13.06.2019
16:15
Arnaud Casteigts
TEL 512
English

Back to the research colloquium site.

Nach oben