Trouver des spanners peu denses dans les cliques temporelles
Jason Schoeters  1@  , Arnaud Casteigts  2@  , Joseph Peters  3@  
1 : Laboratoire dÍnformatique, de Traitement de lÍnformation et des Systèmes
Université Le Havre Normandie, Université de Rouen Normandie : EA4108, Institut national des sciences appliquées Rouen Normandie
2 : Laboratoire Bordelais de Recherche en Informatique
Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1, Université Bordeaux Segalen - Bordeaux 2
3 : School of Computing Science

Nous nous intéressons à une question posée par Kempe, Kleinberg, et Kumar (STOC 2000) : existe-t-il toujours un sous-ensemble d'arêtes peu dense préservant la connexité temporelle dans un graphe dynamique G ? On appelle ces sous-ensembles des spanners temporels de G. Récemment, Axiotis et Fotakis (ICALP 2016) ont répondu négativement, montrant qu'il existe une famille de graphes dynamiques denses n'admettant pas de spanner temporel peu dense. La question est donc de savoir si des spanners peu denses existent pour des classes spécifiques de graphes denses. Dans cet article, nous répondons positivement pour les graphes complets en montrant que ces graphes admettent toujours un spanner de taille O(nlogn). Il s'agit de la première réponse positive de ce type depuis le travail de Kempe et al.


Personnes connectées : 5 Vie privée
Chargement...