Resumen:
El concepto de thinness fue introducido por [Man+07]. 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 ficha 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 está 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 [Man+07] o el problema de coloreo capacitado con aplicación al problema de combinación de recorrido de recogida y entrega [BMO11]. Dado un orden para un grafo, la complejidad de hallar la thinness, para ese orden en particular, es O (n a la potencia 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 [BE18]. 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 i en la cantidad de nodos introduciendo el nuevo concepto de Grupos de Conflicto.
Citación:
---------- APA ----------
Rabinowicz, Lucía; Bonomo, Flavia. (2010). Sobre la thinness de árboles. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000517_Rabinowicz
---------- CHICAGO ----------
Rabinowicz, Lucía; Bonomo, Flavia. "Sobre la thinness de árboles". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2010.https://hdl.handle.net/20.500.12110/seminario_nCOM000517_Rabinowicz
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000517_Rabinowicz.pdf
Distrubución geográfica
