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:-0300
TZOFFSETTO:-0300
TZNAME:-03
DTSTART:20230101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Sao_Paulo:20240415T100000
DTEND;TZID=America/Sao_Paulo:20240415T120000
DTSTAMP:20260519T112108
CREATED:20240408T124937Z
LAST-MODIFIED:20240408T124937Z
UID:9058-1713175200-1713182400@www.dc.uba.ar
SUMMARY:Defensa Tesis Doctorado Carolina Lucía Gonzalez
DESCRIPTION:Título: Problemas localmente verificables parametrizados por treewidth\, clique-width y mim-width\nDirectora: Flavia Bonomo\nConsejero de estudios: Javier Marenco\nJurados:\nDr. Sergio Cabello Justo – Prof. Full\, DMAT\, Univ. de Liubliana\nDra. Paloma T. De Lima – Prof. Asis.\, Univ. de Copenhagen\nDr. Dimítrios Thilikós Touloupas – Dir. de Inv.\, CNRS – LIRMM \nResumen:\nIntuitivamente\, un problema localmente verificable es un problema de partición de vértices (o\, equivalentemente\, de coloreo de vértices) para el cual una solución puede ser verificada simplemente chequeando una determinada propiedad local para cada vértice\, es decir\, una propiedad que involucra solamente la solución restringida al vértice y a sus vecinos. Este es el caso de diversas variantes de los problemas de dominación\, conjunto independiente y k-coloreo\, entre otros. Existen numerosos marcos generales que incluyen un gran subconjunto de estos problemas\, para los cuales se propusieron algoritmos para resolverlos eficientemente en varias clases de grafos.\nEn esta tesis definimos un nuevo marco para problemas localmente verificables\, formalizando la noción intuitiva que tenemos de ellos para luego analizar bajo qué circunstancias podemos proponer algoritmos eficientes que los resuelvan. Los algoritmos propuestos se basan en programación dinámica y para ellos calculamos sus complejidades parametrizadas por treewidth\, clique-width y mim-width. Los resultados obtenidos generalizan aquellos de marcos definidos anteriormente. Mostramos además cómo modelar dentro de nuestro marco diversos problemas de la literatura\, como ser [k]-dominación romana\, k-comunidad y dominación Grundy\, probando así que son FPT o XP parametrizados por treewidth\, clique-width o mim-width. Más aún\, proponemos esquemas de aproximación polinomiales para algunos problemas localmente verificables en grafos planares. \nPalabras claves: problema localmente verificable\, treewidth\, clique-width\, mim-width\, complejidad parametrizada\, esquema de aproximación polinomial.
URL:https://www.dc.uba.ar/event/defensa-tesis-doctorado-carolina-lucia-gonzalez/
LOCATION:Aula 1302
CATEGORIES:Agenda
END:VEVENT
END:VCALENDAR