On the probabilistic min spanning tree problem
Boria, Nicolas; Murat, Cécile; Paschos, Vangelis (2011), On the probabilistic min spanning tree problem, Proceedings of the 2010 International Multiconference on Computer Science and Information Technology (IMCSIT), IEEE, p. 893-900
TypeCommunication / Conférence
Conference titleInternational Multiconference on Computer Science and Information Technology (IMCSIT 2010)
Book titleProceedings of the 2010 International Multiconference on Computer Science and Information Technology (IMCSIT)
MetadataShow full item record
Abstract (EN)We study a probabilistic optimization model for MIN SPANNING TREE, where any vertex vi of the input-graph G(V,E) has some presence probability pi in the final instance G' ⊂ G that will effectively be optimized. Supposing that when this “real” instance G' becomes known, a decision maker might have no time to perform computation from scratch, we assume that a spanning tree T, called anticipatory or a priori spanning tree, has already been computed in G and, also, that a decision maker can run a quick algorithm, called modification strategy, that modifies the anticipatory tree T in order to fit G'. The goal is to compute an anticipatory spanning tree of G such that, its modification for any G' ⊆ G is optimal for G'. This is what we call PROBABILISTIC MIN SPANNING TREE problem. In this paper we study complexity and approximation of PROBABILISTIC MIN SPANNING TREE in complete graphs as well as of two natural subproblems of it, namely, the PROBABILISTIC METRIC MIN SPANNING TREE and the PROBABILISTIC MIN SPANNING TREE 1,2 that deal with metric complete graphs and complete graphs with edge-weights either 1, or 2, respectively.
Subjects / Keywordsmin spanning tree; probabilistic optimization model
Showing items related by title and author.