Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width

Mostrar todas las versiones(2)

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 sola...

Descripción completa

Detalles Bibliográficos
Autor principal: Gonzalez, Carolina Lucía
Otros Autores: Bonomo, Flavia
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2024
Materias:
PROBLEMA LOCALMENTE VERIFICABLE
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
COMPLEJIDAD PARAMETRIZADA
ESQUEMA DE APROXIMACION POLINOMIAL
LOCALLY CHECKABLE PROBLEM
PARAMETERIZED COMPLEXITY
POLYNOMIAL-TIME APPROXIMATION SCHEME
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n7502_Gonzalez
record_format dspace
spelling tesis:tesis_n7502_Gonzalez2025-03-31T21:54:23Z Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width Locally checkable problems parameterized by treewidth, clique-width and mim-width Gonzalez, Carolina Lucía Bonomo, Flavia PROBLEMA LOCALMENTE VERIFICABLE TREEWIDTH CLIQUE-WIDTH MIM-WIDTH COMPLEJIDAD PARAMETRIZADA ESQUEMA DE APROXIMACION POLINOMIAL LOCALLY CHECKABLE PROBLEM TREEWIDTH CLIQUE-WIDTH MIM-WIDTH PARAMETERIZED COMPLEXITY POLYNOMIAL-TIME APPROXIMATION SCHEME 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. 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. Fil: Gonzalez, Carolina Lucía. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2024-04-15 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic PROBLEMA LOCALMENTE VERIFICABLE
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
COMPLEJIDAD PARAMETRIZADA
ESQUEMA DE APROXIMACION POLINOMIAL
LOCALLY CHECKABLE PROBLEM
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
PARAMETERIZED COMPLEXITY
POLYNOMIAL-TIME APPROXIMATION SCHEME
spellingShingle PROBLEMA LOCALMENTE VERIFICABLE
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
COMPLEJIDAD PARAMETRIZADA
ESQUEMA DE APROXIMACION POLINOMIAL
LOCALLY CHECKABLE PROBLEM
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
PARAMETERIZED COMPLEXITY
POLYNOMIAL-TIME APPROXIMATION SCHEME
Gonzalez, Carolina Lucía
Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
topic_facet PROBLEMA LOCALMENTE VERIFICABLE
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
COMPLEJIDAD PARAMETRIZADA
ESQUEMA DE APROXIMACION POLINOMIAL
LOCALLY CHECKABLE PROBLEM
TREEWIDTH
CLIQUE-WIDTH
MIM-WIDTH
PARAMETERIZED COMPLEXITY
POLYNOMIAL-TIME APPROXIMATION SCHEME
description 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.
author2 Bonomo, Flavia
author_facet Bonomo, Flavia
Gonzalez, Carolina Lucía
format Tesis doctoral
Tesis doctoral
publishedVersion
author Gonzalez, Carolina Lucía
author_sort Gonzalez, Carolina Lucía
title Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
title_short Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
title_full Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
title_fullStr Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
title_full_unstemmed Problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
title_sort problemas localmente verificables parametrizados por treewidth, clique-width y mim-width
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2024
url https://hdl.handle.net/20.500.12110/tesis_n7502_Gonzalez
work_keys_str_mv AT gonzalezcarolinalucia problemaslocalmenteverificablesparametrizadosportreewidthcliquewidthymimwidth
AT gonzalezcarolinalucia locallycheckableproblemsparameterizedbytreewidthcliquewidthandmimwidth
_version_ 1831982323511328768

Ejemplares similares