Problemas de dominación de aristas : algoritmos, cotas y propiedades

Mostrar todas las versiones(3)

En esta tesis estudiamos problemas de conjunto dominante mediante dos enfoquesdiferentes: combinatorio y algorítmico. El primero consiste en entender las esctructurasdel grafo relacionadas con la solución mínima y también contar el número de solucionesminimales que un grafo puede admitir. El enfoque...

Descripción completa

Detalles Bibliográficos
Autor principal: Moyano, Verónica Andrea
Otros Autores: Lin, Min Chih
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2017
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6216_Moyano
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6216_Moyano_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n6216_Moyano_oai
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
description En esta tesis estudiamos problemas de conjunto dominante mediante dos enfoquesdiferentes: combinatorio y algorítmico. El primero consiste en entender las esctructurasdel grafo relacionadas con la solución mínima y también contar el número de solucionesminimales que un grafo puede admitir. El enfoque algorítmico busca clasificar los problemasde dominación para diferentes clases de grafos de acuerdo a su complejidad (NPcompletoo polinomial), mientras que también intenta desarrollar algoritmos eficientes queresuelvan estos problemas. Las variantes de problemas de conjunto dominante que consideramosen este trabajo son (i) dominación de aristas (ii) dominación eficiente de aristas (iii) dominación perfecta de aristas y (iv) dominación de vértices. En la literatura tambiénse conoce a los conjuntos eficientemente dominantes con el nombre de matching inducidosdominantes. Para el problema (i) presentamos un algoritmo de tiempo lineal para encontrar un conjuntodominante de aristas mínimo para los grafos de intervalos propios. Para el problema (ii) probamos cotas ajustadas para el número de matching inducidos dominantes y tambiéndescribimos los grafos maximales para la clase general de grafos, grafos sin triángulos ygrafos conexos. Para el problema (iii) presentamos un algoritmo de tiempo lineal pararesolver el problema de dominación perfecta de aristas con pesos para los grafos cúbicosque no contienen garras, y un algoritmo robusto, también de tiempo lineal, para los grafosque no contienen P5. El problema (i) es equivalente a (iv) cuando nos restringimos a los grafos de líneas, estosgrafos forman una subclase de los grafos que no contienen K1,3. En la tesis probamosque el problema (iv) es NP-Hard para los grafos bien cubiertos que no contienen K1,4,mientras el problema se resuelve en tiempo lineal para los grafos bien cubiertos que nocontienen K1,3, la cual es una superclase de los grafos bien cubiertos de línea. Finalmente,presentamos algoritmos polinomiales para decidir si un grafo de comparabilidad o su complementoes bien cubierto.
author2 Lin, Min Chih
author_facet Lin, Min Chih
Moyano, Verónica Andrea
format Tesis doctoral
Tesis doctoral
publishedVersion
author Moyano, Verónica Andrea
spellingShingle Moyano, Verónica Andrea
Problemas de dominación de aristas : algoritmos, cotas y propiedades
author_sort Moyano, Verónica Andrea
title Problemas de dominación de aristas : algoritmos, cotas y propiedades
title_short Problemas de dominación de aristas : algoritmos, cotas y propiedades
title_full Problemas de dominación de aristas : algoritmos, cotas y propiedades
title_fullStr Problemas de dominación de aristas : algoritmos, cotas y propiedades
title_full_unstemmed Problemas de dominación de aristas : algoritmos, cotas y propiedades
title_sort problemas de dominación de aristas : algoritmos, cotas y propiedades
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2017
url https://hdl.handle.net/20.500.12110/tesis_n6216_Moyano
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6216_Moyano_oai
work_keys_str_mv AT moyanoveronicaandrea problemasdedominaciondearistasalgoritmoscotasypropiedades
AT moyanoveronicaandrea edgedominatingsetproblemsalgorithmsboundsandproperties
_version_ 1824355975910391808
spelling I28-R145-tesis_n6216_Moyano_oai2024-09-02 Lin, Min Chih Moyano, Verónica Andrea 2017-03-29 En esta tesis estudiamos problemas de conjunto dominante mediante dos enfoquesdiferentes: combinatorio y algorítmico. El primero consiste en entender las esctructurasdel grafo relacionadas con la solución mínima y también contar el número de solucionesminimales que un grafo puede admitir. El enfoque algorítmico busca clasificar los problemasde dominación para diferentes clases de grafos de acuerdo a su complejidad (NPcompletoo polinomial), mientras que también intenta desarrollar algoritmos eficientes queresuelvan estos problemas. Las variantes de problemas de conjunto dominante que consideramosen este trabajo son (i) dominación de aristas (ii) dominación eficiente de aristas (iii) dominación perfecta de aristas y (iv) dominación de vértices. En la literatura tambiénse conoce a los conjuntos eficientemente dominantes con el nombre de matching inducidosdominantes. Para el problema (i) presentamos un algoritmo de tiempo lineal para encontrar un conjuntodominante de aristas mínimo para los grafos de intervalos propios. Para el problema (ii) probamos cotas ajustadas para el número de matching inducidos dominantes y tambiéndescribimos los grafos maximales para la clase general de grafos, grafos sin triángulos ygrafos conexos. Para el problema (iii) presentamos un algoritmo de tiempo lineal pararesolver el problema de dominación perfecta de aristas con pesos para los grafos cúbicosque no contienen garras, y un algoritmo robusto, también de tiempo lineal, para los grafosque no contienen P5. El problema (i) es equivalente a (iv) cuando nos restringimos a los grafos de líneas, estosgrafos forman una subclase de los grafos que no contienen K1,3. En la tesis probamosque el problema (iv) es NP-Hard para los grafos bien cubiertos que no contienen K1,4,mientras el problema se resuelve en tiempo lineal para los grafos bien cubiertos que nocontienen K1,3, la cual es una superclase de los grafos bien cubiertos de línea. Finalmente,presentamos algoritmos polinomiales para decidir si un grafo de comparabilidad o su complementoes bien cubierto. In this thesis we study different dominating set problems with two different approaches:combinatoric and algorithmic. The first one consists in understanding the structure of thegraph with respect to the minimum solution, and in counting the number of minimal solutionsthat the graph can contain. The algorithmic approach classifies the domination problemon different graph classes according to its complexity (NP-complete or polynomialtimesolvable), while it also tries to develop efficient algorithms for the problems. Thevariants of domination problems we consider in this work are (i) edge domination, (ii) efficient edge domination, (iii) perfect edge domination, and (iv) vertex domination. Efficientedge dominating sets are also known in the literature as dominating induced matchings. For (i) we present a linear time algorithm to find a minimum edge dominating seton proper interval graphs. For (ii) we prove tight bounds for the number of dominatinginduced matching, while we described the extremal graphs for the classes of general,triangle-free, and connected graphs. For (iii) we present a linear time algorithm to solvethe weighted perfect edge dominating set problem for cubic claw-free graphs, and a robustlinear time algorithm for P5-free graphs. Problem (i) is equivalent to (iv) restricted to line graphs, which form a subclass of K1,3-free. We prove that (iv) is NP-Hard for well-covered K1;4-free graphs, while it requireslinear time for well-covered K1,3-free graphs, which is a superclass of well-covered linegraphs. Finally, we present polynomial time algorithms to decide if a comparability graphor its complement is well-covered. Fil: Moyano, Verónica Andrea. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n6216_Moyano spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar Problemas de dominación de aristas : algoritmos, cotas y propiedades Edge dominating set problems: Algorithms, bounds and properties info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n6216_Moyano_oai

Ejemplares similares