On the enumeration of non-dominated spanning trees with imprecise weights - Université de technologie de Compiègne Access content directly
Conference Papers Year : 2023

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

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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 View
73 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More