BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Departamento de Computación - ECPv6.15.18//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20190217T020000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20200909T100000
DTEND;TZID=America/Sao_Paulo:20200909T110000
DTSTAMP:20260518T151247
CREATED:20200903T121013Z
LAST-MODIFIED:20200903T121013Z
UID:6135-1599645600-1599649200@www.dc.uba.ar
SUMMARY:Defensa Tesis Licenciatura Diego de Estrada
DESCRIPTION:Título:  Sobre la thinness y thinness propia de un grafo\nDirectora: Flavia Bonomo\nJurados: Guillermo Durán y Esteban Feuerstein \nFecha: Miércoles 9 de Septiembre de 2020\nHora: 10 hs \nLa defensa va a ser en el aula 9 (virtual) del DC. \nResumen:\nLos grafos con thinness acotada fueron denidos por Mannino\, Oriolo\, Ricci y Chandran como una generalización de los grafos de intervalos\, con el propósito de desarrollar una heurística para el problema de asignación de frecuencias en redes GSM. En esta tesis introducimos el concepto de thinness propia\, tal que los grafos con thinness propia acotada generalizan a los grafos de\nintervalos propios. Estudiamos la complejidad computacional de problemas relacionados al reconocimiento de grafos con thinness y thinness propia acotada por k\, demostrando que\nalgunos son NP-completos y otros polinomiales; aunque los problemas de reconocimiento siguen abiertos incluso para k = 2. El caso k = 1 corresponde a los grafos de intervalos y\nde intervalos propios\, respectivamente\, y por lo tanto se reconocen en tiempo polinomial.\nDescribimos el comportamiento de la thinness y thinness propia bajo las operaciones de grafos unión\, suma\, y producto Cartesiano. Tambien estudiamos la relación entre ambos\nparámetros con otros de la literatura como cutwidth\, linear MIM-width\, y anidamiento de intervalos\, que complementan a resultados previos sobre boxicidad y pathwidth. Finalmente\,\ndescribimos una amplia familia de problemas que pueden resolverse con técnicas de programación dinámica en tiempo polinomial en grafos con thinness acotada\, dada cierta representación\, generalizando a la familia list matrix partition\, y luego para grafos con thinness propia acotada la extendemos para incluir problemas de dominación y sus versiones pesadas. \nPalabras clave: Grafo\, Intervalos\, Thinness\, Complejidad\, Algoritmo.
URL:https://www.dc.uba.ar/event/defensa-tesis-licenciatura-diego-de-estrada/
LOCATION:Aula 9 (virtual)
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR