|
|
 |
|
|
|
|
|
|
Materias dictadas en los
últimos años | Courses |
|
|
|
|
|
|
|
 Algoritmos y Estructuras de Datos Avanzadas |
|
|
|
|
|
Problemas de Grafos y Tratabilidad Computacional |
|
|
|
|
|
Algoritmos y Estructuras de Datos III
| |
|
|
|
|
Tecnología de Bases de Datos
| |
|
|
|
|
Base de Datos
| |
|
|
|
|
Ingeniería de Software II
| |
|
|
|
|
Algoritmos y Estructuras de Datos II
| |
|
|
|
|
|
|
|
|
|
|
|
Temas de Tesis de Licenciatura | Bachelor Thesis Topics |
|
|
|
|
|
|
|
|
|
"Algoritmos eficientes para problemas de clique máximo y de conjuntos independiente máximo en grafos monopolares y grafos unipolares"
Resumen : Se propone en esta tesis, resolver lo más eficientemente posible los problemas de clique máximo y conjunto independiente máximo tanto para la versión sin pesos como para la versión pesada (donde los nodos del grafo tienen pesos asignados) en las siguientes clases de grafos: los grafos monopolares, los grafos unipolares y las clases de grafos relacionadas con las anteriores (conocidas o nuevas a descubrir). Tanto los grafos monopolares como los grafos unipolares son grafos polares que a su vez es una generalización de clases de grafos clásicas de Teoría de Grafos como los grafos bipartitos y grafos split. Hay una diferencia computacionalmente importante entre los grafos monopolares y los grafos unipolares donde el problema del reconocimiento de los primeros es NP-Completo mientras para los segundos existe un algoritmo de tiempo cúbico para reconocerlos. Por ello, sería interesante desarrollar algoritmos robustos que resuelvan los problemas para los grafos monopolares sin saber que si el grafo de entrada es monopolar o no. O bien resuelve el problema en cuestión o bien se da cuenta que el grafo es inválido y en tal caso, ofrecer una evidencia (certificado). |
|
|
|
|
|
|
|
"Reconocer más eficientemente algunas clases de grafos hereditarias"
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. |
|
|
|
|
|
|
|
