Calcul de paramètres minimaux dans les graphes dynamiques.

Arnaud Casteigts (1) , Ralf Klasing (1) , Yessin M. Neggaz (1) , Joseph G Peters (2)

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique
2 SFU.ca - Simon Fraser University = Université Simon Fraser

Dans un travail précédent [1], nous avons présenté un algorithme permettant de calculer un paramètre appelé T -interval connectivity dans les graphes dynamiques qui se présentent sous forme d’une suite de graphes G 1 , G 2 , ..., G δ . Cet algorithme considère les graphes de la suite comme des atomes et les manipule via deux opérations élémentaires : une opération de composition (de deux graphes) et une opération de test (sur un graphe). Cet algorithme est optimal dans le sens où il n’utilise que O(δ) opérations de ce type. Dans cet article, nous généralisons cette approche, en montrant notamment qu’il suffit de définir différemment les opérations de composition et de test pour résoudre immédiatement d’autres problèmes. Nous illustrons cela par l’étude de trois problèmes de minimisation, à savoir BOUNDED-REALIZATION-OF-THE-FOOTPRINT, TEMPORAL-DIAMETER, et ROUND-TRIP-TEMPORAL-DIAMETER, chacun faisant référence à une propriété temporelle importante dans les réseaux dynamiques. [1] A. Casteigts, R. Klasing, Y. M. Neggaz, J. G. Peters. Tester efficacement la T-intervalle connexité dans les graphes dynamiques. CIAC 2015 (English) and ALGOTEL 2015 (French).

Domains: Computer Science [cs]

Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, Joseph G Peters. Calcul de paramètres minimaux dans les graphes dynamiques.. ALGOTEL 2017 - 19èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2017, Quiberon, France. ⟨hal-01517872⟩