Título: Sobre la thinness de árboles

Directora: Flavia Bonomo

Jurado: Dr. Luciano Grippo (IC, UNGS) y Dr. Carlos López Pombo (DC, FCEN, UBA)

Resumen:

El concepto de thinness fue introducido por Mannino, Oriolo, Ricci y Chandran en 2007. Grafos con thinness acotada son una generalización de los grafos de intervalo, que son aquellos con thinness 1.

Para entender el concepto de thinness de un grafo vamos a imaginar a los nodos del mismo como fichitas de un juego donde cada fichita tendrá un conjunto de fichas vecinas. Sea una ficha f que representa el nodo x en el grafo, las fichas vecinas de f serán los nodos adyacentes a x en el grafo. Para calcular la thinness del grafo, asignaremos a cada fichita un número. Luego iremos armando pilas con las fichas de forma tal que siempre se cumpla que al momento de agregar una ficha nueva a una pila cualquiera, si esta ficha tiene fichas vecinas en alguna pila, todas las fichas que se encuentran por encima de la vecina, también son vecinas. El orden en el que se apilan las fichas esta dado por el número asociado a la misma. El valor de la thinness del grafo es la mínima cantidad de pilas posibles, para cualquier orden de las fichas.

En esta tesis vamos a calcular la thinness para grafo con un orden prefijado (thin<(G)), es decir, la mínima cantidad de pilas para un orden fijo de las fichas.

En grafos de thinness acotada, muchos problemas NP-completos pueden ser resueltos en tiempo polinomial, como por ejemplo el problema del conjunto independiente ponderado máximo (Mannino, Oriolo, Ricci y Chandran, 2007) o el problema de coloreo capacitado con aplicación al problema de combinación de recorrido de recogida y entrega (Bonomo, Mattia y Oriolo, 2011).

Dado un orden para un grafo, la complejidad de hallar la thinness, para ese orden en particular, es O(n^3) con n la cantidad de nodos del grafo. Esto es así ya que hallar la thinness del grafo es equivalente a encontrar el coloreo en un grafo auxiliar (asociado al orden) también de n vértices pero que resulta de co-comparabilidad. Es un problema abierto la complejidad computacional de calcular la thinness de un grafo sin un orden prefijado.

En esta tesis se realiza un estudio sobre la thinness para orden fijo en grafos sin ciclos (árboles o bosques). Dado un orden con estructura recursiva para numerar los nodos del árbol (como inorder, preorder, postorder o BFS), calcularemos la thinness en tiempo lineal en la cantidad de nodos introduciendo el nuevo concepto de Grupos de Conflicto.