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.
