Algoritmos y complejidad para algunos problemas de dominación

Mostrar todas las versiones(3)

Los problemas de dominación forman un área de investigación en crecimiento, debidoa la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrarredes sociales, sistemas distribuidos, redes biológicas, problemas de localización deinstalaciones, etc. En esta tesis estudiamos los si...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Mizrahi, Michel Jonathan
Formato: Tesis Doctoral
Lenguaje:Inglés
Publicado: 2014
Materias:
ALGORITMOS
TEORIA DE GRAFOS
CONJUNTO DOMINANTE
COMPLEJIDAD COMPUTACIONAL
ALGORITHMS
GRAPH THEORY
DOMINATING SET
COMPUTATIONAL COMPLEXITY
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5627_Mizrahi
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n5627_Mizrahi
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv Inglés
topic ALGORITMOS
TEORIA DE GRAFOS
CONJUNTO DOMINANTE
COMPLEJIDAD COMPUTACIONAL
ALGORITHMS
GRAPH THEORY
DOMINATING SET
COMPUTATIONAL COMPLEXITY
spellingShingle ALGORITMOS
TEORIA DE GRAFOS
CONJUNTO DOMINANTE
COMPLEJIDAD COMPUTACIONAL
ALGORITHMS
GRAPH THEORY
DOMINATING SET
COMPUTATIONAL COMPLEXITY
Mizrahi, Michel Jonathan
Algoritmos y complejidad para algunos problemas de dominación
topic_facet ALGORITMOS
TEORIA DE GRAFOS
CONJUNTO DOMINANTE
COMPLEJIDAD COMPUTACIONAL
ALGORITHMS
GRAPH THEORY
DOMINATING SET
COMPUTATIONAL COMPLEXITY
description Los problemas de dominación forman un área de investigación en crecimiento, debidoa la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrarredes sociales, sistemas distribuidos, redes biológicas, problemas de localización deinstalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficientepor vértices, (iv) dominación eficiente por aristas (también conocida como matchinginducido dominante), (v) dominación perfecta por vértices (vi) dominación perfectapor aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamentedominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde seprohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos ysimples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circularesfueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentespara el problema (iii). Damos tres algoritmos de tiempo exponencial para resolverel problema (iv) en grafos generales. Además, para el problema (iv), presentamosalgoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos,y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamosalgoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalospropios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafostrapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil paragrafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafossplit, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.
format Tesis Doctoral
author Mizrahi, Michel Jonathan
author_facet Mizrahi, Michel Jonathan
author_sort Mizrahi, Michel Jonathan
title Algoritmos y complejidad para algunos problemas de dominación
title_short Algoritmos y complejidad para algunos problemas de dominación
title_full Algoritmos y complejidad para algunos problemas de dominación
title_fullStr Algoritmos y complejidad para algunos problemas de dominación
title_full_unstemmed Algoritmos y complejidad para algunos problemas de dominación
title_sort algoritmos y complejidad para algunos problemas de dominación
publishDate 2014
url https://hdl.handle.net/20.500.12110/tesis_n5627_Mizrahi
work_keys_str_mv AT mizrahimicheljonathan algoritmosycomplejidadparaalgunosproblemasdedominacion
AT mizrahimicheljonathan algorithmsandcomplexityforsomedominationproblems
_version_ 1782023759575646208
spelling todo:tesis_n5627_Mizrahi2023-10-03T12:59:16Z Algoritmos y complejidad para algunos problemas de dominación Algorithms and complexity for some domination problems Mizrahi, Michel Jonathan ALGORITMOS TEORIA DE GRAFOS CONJUNTO DOMINANTE COMPLEJIDAD COMPUTACIONAL ALGORITHMS GRAPH THEORY DOMINATING SET COMPUTATIONAL COMPLEXITY Los problemas de dominación forman un área de investigación en crecimiento, debidoa la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrarredes sociales, sistemas distribuidos, redes biológicas, problemas de localización deinstalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficientepor vértices, (iv) dominación eficiente por aristas (también conocida como matchinginducido dominante), (v) dominación perfecta por vértices (vi) dominación perfectapor aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamentedominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde seprohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos ysimples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circularesfueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentespara el problema (iii). Damos tres algoritmos de tiempo exponencial para resolverel problema (iv) en grafos generales. Además, para el problema (iv), presentamosalgoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos,y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamosalgoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalospropios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafostrapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil paragrafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafossplit, mientras que las otras dos variantes se pueden resolver en tiempo polinomial. Domination is a growing research area in graph theory, with a vast number ofapplications across different disciplines, which include social networks, distributedcomputing, biological networks, facility location problems, etc. In this thesis westudied the following domination problems (i) minimum dominating set problem (ii) Roman domination (iii) efficient vertex domination (iv) efficient edge domination (also known as dominating induced matching or DIM) (v) perfect vertex domination (vi) perfect edge domination (vii) maximum induced chordal subgraph withoutproperly dominated vertices (also known as cluster vertex deletion). For problem (i) we determined its complexity for graph classes defined by forbidding as inducedsubgraphs all graphs with at most four vertices. We studied problems (i) and (ii) forsome subclasses of P5-free graphs, giving efficient, robust and simple algorithms forboth of them. Linear time algorithms restricted to circular-arc graphs were presentedfor problems (iv), (v), (vi) using existent linear algorithms from problem (iii). Wedescribed three exact exponential time algorithms solving problem (iv) for generalgraphs. Also, for problem (iv), O(n) time algorithms were given restricted to chordal,dually-chordal, bi-convex and claw-free graphs. We studied four variants of problem (vii) and presented efficient algorithms for all variants whenever the graphs wereproper-interval graphs, interval graphs, circular-arc graphs, permutation graphs andtrapezoid graphs. On the other hand we proved that the four variants are NP-Hardfor bipartite graphs. Finally we showed that two of the variants are NP-Hard for splitgraphs while the other two variants are polynomially solvable. Fil: Mizrahi, Michel Jonathan. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2014 Tesis Doctoral PDF Inglés info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n5627_Mizrahi

Ejemplares similares