MST en grafos con incertidumbre y cómo encontrarlos con consultas de mínimo costo.

Abstract: En esta presentación estudiaremos el problema de MST en un contexto donde los pesos son inciertos. Dado un grafo, para cada arista se conocerá un conjunto no vacío que contiene los posibles pesos de la arista. Eventualmente los verdaderos pesos se darán a conocer y llamamos a esto una realización de los pesos. Los algoritmos a considerar tendrán acceso a una operación especial llamada “consulta” que revela de manera inmediata el verdadero peso de una arista a cierto costo predeterminado. Nos enfocaremos en los siguientes problemas:

– El problema de MST uniforme; donde el objetivo es encontrar un árbol que es un MST para todas las posibles realizaciones o determinar que dicho árbol no existe. A estos arboles les llamaremos MST uniformes.

– El problema de consulta factible de costo mínimo. En este problema estamos interesado en encontrar un conjunto de elementos que al consultarlo garantice la existencia de un MST uniforme. Más aún, estamos interesados en hacer esto al mínimo costo posible.

Posted on Aug 20, 2018 in ACGO, Seminars