Título: Sobre la thinness de árboles y otras clases de grafos
Directora: Flavia Bonomo
Co-directora: Carolina Lucía Gonzalez
Jurados: Verónica Becher y Moysés Sampaio

Resumen:
La thinness de un grafo es un parámetro de anchura que generaliza
algunas propiedades de grafos de intervalo, los cuales son
exactamente los grafos con thinness uno. Muchos problemas
NP-completos pueden ser resueltos en tiempo polinomial para grafos
de thinness acotada, dada una representación adecuada. En este
trabajo presentamos una algoritmo constructivo con complejidad
temporal O(n.log(n)) para computar la thinness de un árbol dado,
junto a una solución óptima consistente (orden y partición).
Utilizamos resultados intermedios de esta construcción para
mejorar cotas conocidas de thinness en árboles para algunos casos.
También mostramos la thinness exacta the los grafos corona, y
damos una cota superior para la thinness de otras clases de grafos
(incluyendo grafos grilla). Finalmente, proponemos algunas
heurísticas para construir una solución consistente para algunos
grafos más generales.