Cómputo de la anchura arbórea de un grafo
No Thumbnail Available
Date
2016-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En esta tesis se presentan los conceptos y resultados necesarios para computar la anchura arbórea de un grafo a través de uno de sus árboles de descomposición. Puesto que el concepto de anchura arbórea inicialmente es dado sobre la familia de todos los ´arboles de descomposición del grafo, se presentan resultados de la posibilidad de realizar este computo sobre cualquier elemento de dicha familia. También, se muestra un algoritmo de parámetro fijo tratable (PFT) junto con su implementación en Java. Finalmente, se muestran relaciones de tratabilidad con la posibilidad de expresar una propiedad grafica en lenguaje de lógica monádica de segundo orden y la condición adicional de que la anchura arbórea del grafo sea acotada.”