Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares

Los resultados de esta tesis se enmarcan dentro del área de la Optimización Combinatoria. Principalmente, se conjugan técnicas asociadas a las áreas de Complejidad Computacional, Algoritmos y Teoría de Grafos, entre otras. Se exponen los resultados obtenidos luego del estudio de la complejidad comp...

Descripción completa

Detalles Bibliográficos
Autor principal:	Lopez Pujato, María Inés
Otros Autores:	Leoni, Valeria
Formato:	doctoralThesis Tésis de Doctorado
Lenguaje:	Español
Publicado:	2022
Materias:	Teoría de grafos Dominación Algoritmos Complejidad computacional Grafos arco-circulares
Acceso en línea:	http://hdl.handle.net/2133/23901 http://hdl.handle.net/2133/23901
Aporte de:	Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario

id	I15-R121-2133-23901
record_format	dspace
institution	Universidad Nacional de Rosario
institution_str	I-15
repository_str	R-121
collection	Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR)
language	Español
topic	Teoría de grafos Dominación Algoritmos Complejidad computacional Grafos arco-circulares
spellingShingle	Teoría de grafos Dominación Algoritmos Complejidad computacional Grafos arco-circulares Lopez Pujato, María Inés Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
topic_facet	Teoría de grafos Dominación Algoritmos Complejidad computacional Grafos arco-circulares
description	Los resultados de esta tesis se enmarcan dentro del área de la Optimización Combinatoria. Principalmente, se conjugan técnicas asociadas a las áreas de Complejidad Computacional, Algoritmos y Teoría de Grafos, entre otras. Se exponen los resultados obtenidos luego del estudio de la complejidad computacional para cada número entero positivo k fijo, de las siguientes variantes del problema clásico de dominación en grafos en algunas subclases de los grafos arco-circulares: k-upla dominación, k-dominación y k-dominación total. Para k = 1, todas ellas coinciden con el concepto usual de dominación, 1-dominación o dominación total en grafos. Desde el punto de vista de la complejidad computacional de problemas de decisión, estas variantes de la dominación clásica son "difíciles” de resolver. Como es habitual, se planteó entonces estudiar subclases donde los problemas sean tratables, es decir, resolubles a través de un algoritmo eficiente (de tiempo de ejecución u orden polinomial en el tamano de las instancias). Se investigaron instancias dadas por clases de grafos para los cuales existen en la literatura algoritmos que resuelven el problema para k = 1 en tiempo polinomial y que su tratamiento estaba abierto para los restantes valores de k enteros o bien, que disponen de un tal algoritmo pero el mismo es poco eficiente en algún sentido. Si bien los problemas abordados generalizan los diferentes conceptos de dominación, los algortimos que presentamos en esta tesis no son una generalización de los existentes en la literatura para el problema de dominación usual. Aún notando que la diferencia en las definiciones de los problemas estudiados es muy sutil, la estructura intrínseca de cada clase de grafos abordada mostró que en general no es sencillo, o bien no es posible, aplicar el mismo tratamiento a las tres variantes del problema estudiado en esas clases. Más precisamente, en esta tesis se desarrollan: para la k-dominación y k-dominación total y sus versiones ponderadas, un algoritmo específico de orden polinomial en función de k para la clase de los grafos de intervalos propios; para la k-upla dominación, sendos algoritmos eficientes para dos subclases de grafos arco-circulares, la de los grafos co-biconvexos y la de los grafos web, instancias para las que no se contaba hasta el momento con un algoritmo de resolución.
author2	Leoni, Valeria
author_facet	Leoni, Valeria Lopez Pujato, María Inés
format	doctoralThesis Tésis de Doctorado
author	Lopez Pujato, María Inés
author_sort	Lopez Pujato, María Inés
title	Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
title_short	Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
title_full	Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
title_fullStr	Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
title_full_unstemmed	Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
title_sort	sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares
publishDate	2022
url	http://hdl.handle.net/2133/23901 http://hdl.handle.net/2133/23901
work_keys_str_mv	AT lopezpujatomariaines sobrevariacionesdelproblemadekdominacionenalgunassubclasesdegrafosarcocirculares
bdutipo_str	Repositorios
_version_	1764820411726430210

Sobre variaciones del problema de k-dominación en algunas subclases de grafos arco-circulares

Ejemplares similares