On the enumeration of non-dominated spanning trees with imprecise weights - Université de technologie de Compiègne Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

On the enumeration of non-dominated spanning trees with imprecise weights

Résumé

Many works within robust combinatorial optimisation consider interval-valued costs or constraints. While most of these works focus on finding unique solutions such as minimax ones, a few consider the problem of characterising a set of non-dominated optimal solutions. This paper is situated within this line of work, and consider the problem of exactly enumerating the set of non-dominated spanning trees under interval-valued costs. We show in particular that each tree in this set can be obtained through a polynomial procedure, and provide an efficient algorithm to achieve the enumeration.
Fichier principal
Vignette du fichier
main.pdf (339.82 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04155185 , version 1 (07-07-2023)

Identifiants

Citer

Tom Davot, Sébastien Destercke, David Savourey. On the enumeration of non-dominated spanning trees with imprecise weights. 17th European Conference on Symbolic and Quantitative Approaches to Reasoning and Uncertainty (ECSQARU 2023), Sep 2023, Arras, France. pp.348-358, ⟨10.1007/978-3-031-45608-4_26⟩. ⟨hal-04155185⟩
51 Consultations
73 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More