04/02/2025
Reconocer más eficientemente algunas clases de grafos hereditarias
Min Chih Lin
Resumen
Una clase de grafos es hereditaria si todos los subgrafos inducidos de cualquier grafo miembro de la clase también son miembros. Se sabe que toda clase hereditaria tiene una caracterización por subgrafos inducidos prohibidos. Por otro lado, para una clase no hereditaria X, se puede definir una subclase hereditaria de X llamada X hereditaria. Proponemos desarrollar en esta tesis algoritmos de reconocimiento más eficientes para algunas clases de grafos que poseen una caracterización por una cantidad finita de subgrafos inducidos prohibidos. Claramente, al ser una cantidad finita de subgrafos entonces existe un algoritmo trivial de complejidad temporal O(|V|^k) donde k es la cantidad de nodos del subgrafo prohibido con mayor cantidad de nodos y V es el conjunto de vértices del grafo a reconocer. Los algoritmos a desarrollar deben ser significativamente mejores que los triviales. Particularmente, vamos a considerar dos clases de grafos hereditarias como base: los grafos vecindad cerrada Helly hereditaria y los grafos vecindad abierta Helly hereditaria.
Descripción de la propuesta
—
Conocimientos deseables
Teoría y Algoritmos en grafos
Qué aprenderá el o la estudiante
Aprenderá cómo realizar una investigación orientada a algorítmica en grafos
