Temporal Cliques Admit Sparse Spanners
| Autor: | Casteigts, Arnaud, Peters, Joseph G., Schoeters, Jason |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G=(V,E)$ be an undirected graph on $n$ vertices and $\lambda:E\to 2^{\mathbb{N}}$ a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is {\em 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 \cite{KKK02} asked whether, given such a temporal graph, a {\em sparse} subset of edges always exists whose labels suffice to preserve temporal connectivity -- a {\em temporal spanner}. Axiotis and Fotakis \cite{AF16} answered negatively by exhibiting a family of $\Theta(n^2)$-dense temporal graphs which admit no temporal spanner of density $o(n^2)$. In this paper, we give the first positive answer as to the existence of $o(n^2)$-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if $G$ is a complete graph, then one can always find a temporal spanner of density $O(n \log n)$. Comment: This version of the article will appear in JCSS and a short version with the same title was presented at ICALP 2019 |
| Databáze: | arXiv |
| Externí odkaz: |
|