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.
Palabras clave. clase hereditaria de grafos; subgrafo inducido; reconocimiento de grafos; algoritmo eficiente
Conocimientos deseables. Teoría y Algoritmos en grafos
¿Qué podría aprender quien realice esta tesis? – Aprenderá cómo realizar una investigación orientada a algorítmica en grafos.
Dirección de la tesis
Lin, Min Chih
Departamento de Computación e Instituto de Cálculo
Contacto: oscarlin@dc.uba.ar
Descargar PDF
Reconocer más eficientemente algunas clases de grafos hereditarias