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⟩
41 View
54 Download

Altmetric

Share

Gmail Facebook X LinkedIn More