Catálogo de publicaciones - tesis
Título de Acceso Abierto
Problemas de dominación de aristas: algoritmos, cotas y propiedades
Verónica Andrea Moyano Min Chih Lin
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
En esta tesis estudiamos problemas de conjunto dominante mediante dos enfoques diferentes: combinatorio y algorítmico. El primero consiste en entender las esctructuras del grafo relacionadas con la solución mínima y también contar el número de soluciones minimales que un grafo puede admitir. El enfoque algorítmico busca clasificar los problemas de dominación para diferentes clases de grafos de acuerdo a su complejidad (NPcompleto o polinomial), mientras que también intenta desarrollar algoritmos eficientes que resuelvan estos problemas. Las variantes de problemas de conjunto dominante que consideramos en 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én se conoce a los conjuntos eficientemente dominantes con el nombre de matching inducidos dominantes. Para el problema (i) presentamos un algoritmo de tiempo lineal para encontrar un conjunto dominante 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én describimos los grafos maximales para la clase general de grafos, grafos sin triángulos y grafos conexos. Para el problema (iii) presentamos un algoritmo de tiempo lineal para resolver el problema de dominación perfecta de aristas con pesos para los grafos cúbicos que no contienen garras, y un algoritmo robusto, también de tiempo lineal, para los grafos que no contienen P5. El problema (i) es equivalente a (iv) cuando nos restringimos a los grafos de líneas, estos grafos forman una subclase de los grafos que no contienen K1,3. En la tesis probamos que 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 no contienen 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 complemento es bien cubierto.Palabras clave – provistas por el repositorio digital
No disponibles.
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2017 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2017-03-29
Información sobre licencias CC