Tesis
Última actualización: Mar 20, 2022
El problema que ataqué en mi tesis se puede describir de la siguiente forma
Enunciado del problema Sea un ciclo de n nodos \(C=(V,E_0)\), y un conjunto de aristas \(E\) tales que al agregárselas al ciclo se forma un grafo \(3\)-nodo-conexo. Queremos estudiar el problema de agregar la menor cantidad de aristas de \(E\) para dejar al ciclo \(3-\)nodo-conexo. Es decir, queremos encontrar un conjunto factible de aristas \(F \subseteq E\) de menor tamaño posible tal que \(C'=(V,E_0 \cup F)\) sea \(3-\)nodo-conexo.
Fecha de defensa: 28 de mayo de 2021
Objetivos
- Estudiar la complejidad del problema de aumentar la nodo-conectividad de un ciclo.
- Estudiar la formulación del problema de programación lineal que define el problema.
- Diseñar algoritmos de aproximación que permitan resolver el problema.