Registro:
| Documento: | Tesis de Grado |
| Título: | On the thinness of trees and other graph classes = Sobre la thinness de árboles y otras clases de grafos |
| Autor: | Brandwein, Eric; Sansone, Agustín |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2022 |
| Fecha en portada: | 19 de Marzo 2022 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Bonomo, Flavia |
| Director Asistente: | González, Carolina Lucía |
| Jurado: | Becher, Verónica Andrea; Sampaio, Moysés |
| Idioma: | Inglés |
| Palabras clave: | ARBOLES; THINNESS; ALGORITMO POLINOMIAL; GRAFOS CORONA; GRAFOS GRILLA; HEURISTICASTREES; THINNESS; POLYNOMIAL ALGORITHM; CROWN GRAPHS; GRID GRAPHS; HEURISTICS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000556_BrandweinSansone |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000556_BrandweinSansone.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000556_BrandweinSansone |
| Ubicación: | Dep.COM 000556 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Brandwein, Eric; Sansone, Agustín. (2022). On the thinness of trees and other graph classes = Sobre la thinness de árboles y otras clases de grafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000556_BrandweinSansone |
Resumen:
La thinness de un grafo es un parámetro de anchura que generaliza algunas propiedades de grafos de intervalo, los cuales son exactamente los grafos con thinness uno. Muchos problemas NP-completos pueden ser resueltos en tiempo polinomial para grafos de thinness acotada, dada una representación adecuada. En este trabajo presentamos una algoritmo constructivo con complejidad temporal O(n log(n)) para computar la thinness de un árbol dado, junto a una solución óptima consistente (orden y partición). Utilizamos resultados intermedios de esta construcción para mejorar cotas conocidas de thinness en árboles para algunos casos. También mostramos la thinness exacta de los grafos corona CRn, y damos una cota superior para la thinness de otras clases de grafos (incluyendo grafos grilla GRr). Finalmente, proponemos algunas heurísticas para construir una solución consistente para algunos grafos más generales.
Abstract:
The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. In this work we present a constructive O(n log(n))-time algorithm to compute the thinness for any given tree, along with an optimal consistent solution (ordering and partition). We use some intermediate results of this construction to improve known bounds of the thinness in some special trees. We also show the exact thinness of crown graphs CRn, and give new upper bounds for the thinness of other graph classes (including grids GRr). Finally, we propose some heuristics to construct a consistent solution for some more general graphs.
Citación:
---------- APA ----------
Brandwein, Eric; Sansone, Agustín. (2022). On the thinness of trees and other graph classes = Sobre la thinness de árboles y otras clases de grafos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000556_BrandweinSansone
---------- CHICAGO ----------
Brandwein, Eric; Sansone, Agustín. "On the thinness of trees and other graph classes = Sobre la thinness de árboles y otras clases de grafos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2022.https://hdl.handle.net/20.500.12110/seminario_nCOM000556_BrandweinSansone
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000556_BrandweinSansone.pdf
Distrubución geográfica
