Stochastic maximum weight forest problem

Pablo Adasme, Rafael Andrade, Marc Letournel, Abdel Lisser
  • Networks, March 2015, Wiley
  • DOI: 10.1002/net.21610

Stochastic maximum weight forests

What is it about?

We discuss how to obtain connected acyclic components (a forest) maximizing the sum of their edge weights. The extra ingredient is that some edges have deterministic weight while others have uncertain weights in a given undirected graph.

Why is it important?

This work presents a correct understanding of the Martin's spanning tree polytope introduced in the 90's and extends his idea to forests.


Professor Rafael Castro de Andrade (Author)
Universidade Federal do Ceara

From a theoretical point of view, this work opens new perspectives to use the Martin's sub-tour elimination constraints to model acyclic structures in general multi-graphs containing both edges or arcs in its set of connections.

The following have contributed to this page: Professor Rafael Castro de Andrade and Professor Abdel Lisser