Confiabilidad de grafos con dos terminales con fallas en vértices

Abstract

En este trabajo se estudia la inexistencia de grafos uniformemente más confiables para comunicar a dos terminales bajo restricción de distancia 5 entre los terminales. Se proponen tres enfoques complementarios: (i) desarrollo de una estrategia de demostración basada en técnicas de optimización matricial y transformaciones sobre grafos, (ii) aplicando un método de optimización basado en Variable Neighborhood Search (VNS), y (iii) verificación computacional de la conjetura de Brown para familias finitas de grafos mediante un algoritmo de búsqueda local VNS sobre familias concretas de grafos con dos terminales.