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

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2017-03-29

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

spa

Descripción:

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.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n6216_Moyano