Resumen

En el área de complejidad parametrizada se mide el tiempo que toma un algoritmo no sólo en el tamaño de la entrada, sino también en un entero que es parte de la entrada, llamado parámetro, que puede describir la entrada. Un gran objetivo es encontrar algoritmos que resuelvan problemas en tiempo polinomial cuando el parámetro es un entero fijo. 

La thinness es un parámetro de grafos definido en el 2006 que generaliza el concepto de grafos de intervalos. En una clase de grafos con thinness acotada se pueden resolver muchos problemas NP-completos en tiempo polinomial, es decir, hay algoritmos parametrizados por thinness que son muy eficientes. Lamentablemente, calcular la thinness de un grafo es un problema NP-completo. En este trabajo introducimos un nuevo parámetro de grafos, el cluster module number (cm), y luego definimos algoritmos parametrizados por cm que encuentran la thinness de un grafo en tiempo polinomial. Además, damos cotas inferiores de complejidad de algoritmos parametrizados para Thinness cuando el parámetro de entrada cumple algunas propiedades específicas.