1 Search Results for "Peters, Joseph G."

Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
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)

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

  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}
  • Refine by Author
  • 1 Casteigts, Arnaud
  • 1 Peters, Joseph G.
  • 1 Schoeters, Jason

  • Refine by Classification
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 1 Dynamic networks
  • 1 Sparse spanners
  • 1 Temporal connectivity
  • 1 Temporal graphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019