BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Departamento de Computación
X-ORIGINAL-URL:https://www.dc.uba.ar
X-WR-CALDESC:Eventos para Departamento de Computación
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Sao_Paulo
BEGIN:STANDARD
TZOFFSETFROM:-0200
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20180218T020000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0300
TZOFFSETTO:-0200
TZNAME:-02
DTSTART:20181104T030000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0200
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20190217T020000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20190619T170000
DTEND;TZID=America/Sao_Paulo:20190619T180000
DTSTAMP:20260614T165006
CREATED:20190618T125612Z
LAST-MODIFIED:20190618T125612Z
UID:5317-1560963600-1560967200@www.dc.uba.ar
SUMMARY:Defensa Tesis Licenciatura Lucía Rabinowicz
DESCRIPTION:Título: Sobre la thinness de árboles \nDirectora: Flavia Bonomo \nJurado: Dr. Luciano Grippo (IC\, UNGS) y Dr. Carlos López Pombo (DC\, FCEN\, UBA) \nResumen: \nEl 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. \nPara 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. \nEn 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. \nEn 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). \nDado 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. \nEn 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.
URL:https://www.dc.uba.ar/event/defensa-tesis-licenciatura-lucia-rabinowicz/
LOCATION:Aula 3
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR