Skip to Main content Skip to Navigation
Conference papers

Minimum Spanning Trees in Weakly Dynamic Graphs

Moustafa Nakechbandi 1 Jean-Yves Colin 1 Hervé Mathieu
1 RI2C - LITIS - Equipe Réseaux d'interactions et Intelligence Collective
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
Abstract : In this paper, we study weakly dynamic undirected graphs, that can be used to represent some logistic networks. The goal is to deliver all the delivery points in the network. The network exists in a mostly stable environment, except for a few edges known to be non-stable. The weight of each of these non-stable edges may change at any time (bascule or lift bridge, elevator, traffic congestion...). All other edges have stable weights that never change. This problem can be now considered as a Minimum Spanning Tree (MST) problem on a dynamic graph. We propose an efficient polynomial algorithm that computes in advance alternative MSTs for all possible configurations. No additional computation is then needed after any change in the problem because the MSTs are already known in all cases. We use these results to compute critical values for the non-stable weights and to pre-compute best paths. When the non-stable weights change, the appropriate MST may then directly and immediately be used without any recomputation.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02094631
Contributor : Moustafa Nakechbandi <>
Submitted on : Tuesday, April 9, 2019 - 5:44:53 PM
Last modification on : Thursday, March 5, 2020 - 3:30:37 PM

File

logistica17.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02094631, version 1
  • ARXIV : 1904.05066

Citation

Moustafa Nakechbandi, Jean-Yves Colin, Hervé Mathieu. Minimum Spanning Trees in Weakly Dynamic Graphs. LOGISTIQUA 2017, 10th International Colloquium of Logistics and Supply Chain Management, Apr 2017, Rabat, Morocco. ⟨hal-02094631⟩

Share

Metrics

Record views

49

Files downloads

87