Registro:
| Documento: | Tesis Doctoral |
| Título: | Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width |
| Título alternativo: | Locally checkable problems parameterized by treewidth, clique-width and mim-width |
| Autor: | Gonzalez, Carolina Lucía |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2024-04-15 |
| Fecha en portada: | 15 de abril de 2024 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonomo, Flavia |
| Consejero: | Marenco, Javier Leonardo |
| Jurado: | Cabello Justo, Sergio; Lima, Paloma T. De; Thilikós Touloupas, Dimítrios |
| Idioma: | Español |
| Palabras clave: | PROBLEMA LOCALMENTE VERIFICABLE; TREEWIDTH; CLIQUE-WIDTH; MIM-WIDTH; COMPLEJIDAD PARAMETRIZADA; ESQUEMA DE APROXIMACION POLINOMIALLOCALLY CHECKABLE PROBLEM; TREEWIDTH; CLIQUE-WIDTH; MIM-WIDTH; PARAMETERIZED COMPLEXITY; POLYNOMIAL-TIME APPROXIMATION SCHEME |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n7502_Gonzalez.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n7502_Gonzalez |
| Ubicación: | COM 007502 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Gonzalez, Carolina Lucía. (2024). Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez |
Resumen:
Intuitivamente, 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. En 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.
Abstract:
Intuitively, a locally checkable problem is a vertex partition problem (or, equivalently, a vertex coloring problem) for which a solution can be verified simply by checking a certain local property for each vertex, that is, a property that involves only the solution restricted to the vertex and its neighbors. This is the case of several variants of domination, independent set and k-coloring, among other problems. There exist numerous frameworks that include a large subset of these problems, for which algorithms have been proposed to solve them efficiently in various graph classes. In this thesis we define a new framework for locally checkable problems, formalizing the intuitive notion we have of them to then analyze under what circumstances we can propose efficient algorithms to solve them. The proposed algorithms are based on dynamic programming and we computed their complexities when parameterized by treewidth, clique-width and mim-width. The results obtained generalize those of previously defined frameworks. We further show how to model within our framework several problems in the literature, such as [k]-Roman domination, k-community and Grundy domination, thus proving that they are FPT or XP when parameterized by treewidth, clique-width or mim-width. Moreover, we propose polynomial-time approximation schemes for some locally checkable problems in planar graphs.
Citación:
---------- APA ----------
Gonzalez, Carolina Lucía. (2024). Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez
---------- CHICAGO ----------
Gonzalez, Carolina Lucía. "Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2024.https://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n7502_Gonzalez.pdf
