Tesis > Documento


Ver el documento (formato PDF)   Mizrahi, Michel Jonathan.  "Algoritmos y complejidad para algunos problemas de dominación"  (2014-11-21)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Los problemas de dominación forman un área de investigación en crecimiento, debido a la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrar redes sociales, sistemas distribuidos, redes biológicas, problemas de localización de instalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficiente por vértices, (iv) dominación eficiente por aristas (también conocida como matching inducido dominante), (v) dominación perfecta por vértices (vi) dominación perfecta por aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamente dominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde se prohiben 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 y simples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circulares fueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentes para el problema (iii). Damos tres algoritmos de tiempo exponencial para resolver el problema (iv) en grafos generales. Además, para el problema (iv), presentamos algoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos, y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamos algoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalos propios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafos trapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil para grafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafos split, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.

Abstract:
Domination is a growing research area in graph theory, with a vast number of applications across different disciplines, which include social networks, distributed computing, biological networks, facility location problems, etc. In this thesis we studied 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 without properly dominated vertices (also known as cluster vertex deletion). For problem (i) we determined its complexity for graph classes defined by forbidding as induced subgraphs all graphs with at most four vertices. We studied problems (i) and (ii) for some subclasses of P5-free graphs, giving efficient, robust and simple algorithms for both of them. Linear time algorithms restricted to circular-arc graphs were presented for problems (iv), (v), (vi) using existent linear algorithms from problem (iii). We described three exact exponential time algorithms solving problem (iv) for general graphs. 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 were proper-interval graphs, interval graphs, circular-arc graphs, permutation graphs and trapezoid graphs. On the other hand we proved that the four variants are NP-Hard for bipartite graphs. Finally we showed that two of the variants are NP-Hard for split graphs while the other two variants are polynomially solvable.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Algoritmos y complejidad para algunos problemas de dominación     =    Algorithms and complexity for some domination problems
Autor : Mizrahi, Michel Jonathan
Director : Lin, Min Chih
Consejero : Lin, Min Chih
Jurados : Milanic, Martín  ; Nasini, Graciela L.  ; Bonomo, Flavia
Año : 2014-11-21
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Instituto de Cálculo (IC)
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5627_Mizrahi
Idioma : Inglés
Area Temática : Computación / Teoría de la Computabilidad
Computación / Teoría de Grafos
Computación / Teoría Algorítmica de la Información
Palabras claves : ALGORITMOS; TEORIA DE GRAFOS; CONJUNTO DOMINANTE; COMPLEJIDAD COMPUTACIONAL; ALGORITHMS; GRAPH THEORY; DOMINATING SET; COMPUTATIONAL COMPLEXITY
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34