Seminario Avanzado de Teoría de Grafos

Dra. Flavia Bonomo

 

 

 

 

CUATRIMESTRE: Segundo de 2012

HORARIO: Miércoles de 19 a 22hs teóricas; Lunes 11.30 a 13.30hs seminarios.

LUGAR: Aula 6 pabellón I (Miércoles), Aula 12 pabellón I (Lunes).

PRIMERA CLASE: Miércoles 15 de agosto 19hs.

PUNTAJE: 2 puntos

ASIGNATURAS CORRELATIVAS: Algoritmos y Estructuras de Datos III

 

Objetivos:

Se propone esta materia optativa que puede ser ofrecida a estudiantes de la Licenciatura y el Doctorado en Computación y en Matemática. Se requieren para poder cursarla conocimientos básicos en teoría de grafos.
Los objetivos de esta materia son diversos. Por un lado se pretende introducir a los alumnos en tópicos avanzados en teoría de grafos a fin de que puedan descubrir nuevos temas para realizar sus tesis sumándose al grupo que está trabajando en el Departamento en esta área. Por otro lado, completar la formación en grafos puede ser importante para aquellos que piensan hacer investigación en otra área pero que algunos de estos temas les pueden resultar de utilidad para su aplicación en otros campos de la Informática o de la Matemática. Por último, el familiarizarse con la metodología empleada para atacar los problemas que surgen en este tópico puede ser de utilidad para todo estudiante que tiene intenciones de dedicarse a la investigación científica.
La propuesta es realizar la materia con una modalidad de seminario, es decir que el Profesor debe introducir los temas teóricos para luego los estudiantes presentar en clase distintos trabajos de actualidad en estos temas. También se propone discutir en clase sobre algunos problemas abiertos. La materia finaliza con una evaluación final donde se haga una revisión sobre todo lo visto en el cuatrimestre.

 

Programa:

Unidad 1: Grafos de intersección. Definición. Estudio de diferentes clases: cordales, de intervalos, clique, arco-circulares, circulares, de permutación. Algoritmos para problemas famosos sobre estas clases de grafos, aplicaciones y problemas abiertos.

Unidad 2: Clases de grafos definidas por subgrafos prohibidos. Familias finitas e infinitas. Ejemplos de grafos que pueden ser definidos de esta manera: línea, claw-free, split, de comparabilidad, soles. Algoritmos para problemas famosos sobre estas clases de grafos, aplicaciones y problemas abiertos.

Unidad 3: Descomposición de grafos. Descomposición de grafos claw-free. Descomposición modular, treewidth, pathwidth, cliquewidth, boolean width, thinness. Aplicaciones algorítmicas.


Bibliografía básica:

Brandstadt A., Bang Le V. and Spinrad J., Graph classes: A survey, SIAM, 1999.

Eger S., Regular Languages, Tree width and Courcelle's Theorem, VDM Verlag Dr. Müller e.K., 2008.

Fishburn P.C., Interval orders and interval graphs: a study of partially ordered sets, Interval orders and interval graphs: a study of partially ordered sets, 1985.

Golumbic M.C., Algorithmic graph theory and perfect graphs, Annals of Discrete Mathematics, Vol 57, 2004.

McKee T. and McMorris F., Topics in intersection graph theory, SIAM, 1999.

Además, varios papers clásicos y actuales.