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

Detalles Bibliográficos
Autor principal:	Mizrahi, Michel Jonathan
Otros Autores:	Lin, Min Chih
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Inglés
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5627_Mizrahi_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n5627_Mizrahi_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	Inglés
orig_language_str_mv	eng
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.
author2	Lin, Min Chih
author_facet	Lin, Min Chih Mizrahi, Michel Jonathan
format	Tesis doctoral Tesis doctoral publishedVersion
author	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
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2014
url	https://hdl.handle.net/20.500.12110/tesis_n5627_Mizrahi https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n5627_Mizrahi_oai
work_keys_str_mv	AT mizrahimicheljonathan algoritmosycomplejidadparaalgunosproblemasdedominacion AT mizrahimicheljonathan algorithmsandcomplexityforsomedominationproblems
_version_	1824355934782095360
spelling	I28-R145-tesis_n5627_Mizrahi_oai2024-09-02 Lin, Min Chih Mizrahi, Michel Jonathan 2014-11-21 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. application/pdf https://hdl.handle.net/20.500.12110/tesis_n5627_Mizrahi eng 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 ALGORITMOS TEORIA DE GRAFOS CONJUNTO DOMINANTE COMPLEJIDAD COMPUTACIONAL ALGORITHMS GRAPH THEORY DOMINATING SET COMPUTATIONAL COMPLEXITY Algoritmos y complejidad para algunos problemas de dominación Algorithms and complexity for some domination problems 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_n5627_Mizrahi_oai

Algoritmos y complejidad para algunos problemas de dominación

Ejemplares similares