Temas avanzados en algoritmos de grafos
Este archivo contiene material sobre el curso "Temas Avanzados en Algoritmos de Gráficos"
impartido por Ron Shamir en el departamento de Ciencias de la Computación
de la universidad de Tel-Aviv , el 10 / 91-2 / 92 (otoño
92), 4-6 / 94 ( Spring 94) y 4-6 / 97 (Spring 97). Este fue un curso
de posgrado de un semestre abierto también para personas mayores, con una reunión de tres horas cada
semana.
El curso hizo hincapié
en los aspectos algorítmicos
y estructurales de las familias de gráficos
"agradables", en particular gráficos perfectos, gráficos
de intervalos, gráficos
de acordes y gráficos
de comparabilidad.
En el otoño de 92, el curso se basó en gran medida en el libro clásico de Martin C. Golumbic "Teoría de
gráficos algorítmicos
y gráficos perfectos" (Academic Press,
1980), y en algunas partes también en el manuscrito
"El arte de la combinatoria", por Douglas B. West.
Los cursos Spring 94 y Spring 97 tuvieron
una base similar, pero enfatizaron material más reciente e hicieron muchas referencias a aplicaciones en biología molecular. (Consulte la página
web Algoritmos para Biología
Molecular
Conferencia # 1: Introducción a la teoría de grafos
Clase n.2: Gráficos perfectos.
Clase n.3: Gráficos perfectos
y triangulados.
Clase n.4: Reconocer gráficas trianguladas
Clase n.5: Los gráficos
triangulados son perfectos.
Clase n.6: Algoritmos para gráficos triangulados y gráficos de
comparabilidad.
Clase n.7: Gráficos ordenados únicamente de
forma parcial
Clase n.8: algunas familias de gráficos interesantes caracterizadas por intersecciones.
Clase n.9: Gráficos de comparabilidad
Clase n.10: invariantes de comparabilidad y gráficas
de intervalo
Conferencia # 11: Gráficos
de intervalos
Conferencia # 12: Razonamiento
temporal
Por favor envíe todos los comentarios y comentarios a:
rshamir@tau.ac.il
Volver a la página
de inicio de Ron
© Universidad de Tel-Aviv.