Back to Search
Start Over
Temporal cliques admit sparse spanners.
- Source :
-
Journal of Computer & System Sciences . Nov2021, Vol. 121, p1-17. 17p. - Publication Year :
- 2021
-
Abstract
- Let G = (V , E) be an undirected graph on n vertices and λ : E → 2 N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G = (G , λ) is 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 [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ (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 with O (n log n) edges. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COMPLETE graphs
*SPARSE graphs
*WRENCHES
*UNDIRECTED graphs
*GRAPH connectivity
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 121
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 150666185
- Full Text :
- https://doi.org/10.1016/j.jcss.2021.04.004