Sobre la thinness en un grafo

Mostrar todas las versiones(2)

La thinness de un grafo, definida inicialmente en 2007, es un invariante que generaliza a los grafos de intervalos. Todo grafo tiene un valor numérico de thinness y los grafos con thinness 1 coinciden con los grafos de intervalos. Un grafo es k-thin si sus vértices pueden ordenarse de manera que exi...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Brito, Gastón
Otros Autores:	Bonomo, Flavia
Formato:	Tesis de grado publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2020
Materias:	GRAFO THINNESS INTERVALO BOXICITY INTERSECCION BANDWIDTH SMT Z3 GRAPH INTERVAL INTERSECTION
Acceso en línea:	https://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000574_Brito_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-seminario_nCOM000574_Brito_oai
record_format	dspace
spelling	I28-R145-seminario_nCOM000574_Brito_oai2025-08-20 Bonomo, Flavia Brito, Gastón 2020 La thinness de un grafo, definida inicialmente en 2007, es un invariante que generaliza a los grafos de intervalos. Todo grafo tiene un valor numérico de thinness y los grafos con thinness 1 coinciden con los grafos de intervalos. Un grafo es k-thin si sus vértices pueden ordenarse de manera que exista una partición de los v´ertices en k clases cumpliendo que para cada tripla de vértices r < s < t si r y s pertenecen a la misma clase y existe una arista entre r y t, entonces existe una arista entre s y t. La thinness es el menor valor de k tal que el grafo sea k-thin. En este trabajo definimos un modelo de intersección para los grafos con thinness y thinness propia menor o igual a 2 restringiendo los grafos con boxicity 2. Se caracterizan los grafos k-thin y k-thin propios utilizando propiedades de la matriz de adyacencia. Se acota la thinness en relación al bandwidth de un grafo y se hace un resumen de las relaciones conocidas. Se calcula la thinness utilizando SAT Module Theory (SMT), tanto para determinar si vale la propiedad k-thin como para obtener el valor de la thinness mediante optimización. Se evalúa la performance sobre familias de grafos con los resolvedores Z3 Theorem Solver y OptiMathSat. Adicionalmente se utilizan las mismas técnicas para calcular una representación como una intersección de rectángulos en el plano. The thinness of a graph, initially defined in 2007, is an invariant that generalizes the concept of an interval graph. Every graph has a numeric value of thinness and the graphs with thinness 1 are exactly the interval graphs. A graph is k-thin if its vertices can be sorted in a way that exists a partition with k classes with the property that for each triplet of vertices r < s < t if r and s belong to the same class and there is an edge between r y t, then an edge must exist between s and t. The thinness is the least value of k such that the graph is k-thin. In this work we define an intersection model for graphs with thinness and proper thinness lower or equal than 2 by restricting graphs with boxicity 2. The properties of adjacency matrices are used to characterize k-thin and proper k-thin graphs. A bound of the thinness with the bandwidth is obtained and a summary of the known relations is made. It is shown how to calculate the thinness with SAT Module Theory (SMT), both for checking the k-thin property and obtaining the thinness value with optimization. The performance of the Z3 Theorem Solver and OptiMathSat are analized. Additionally the same techniques are used to obtain a representation as an intersection of rectangles on the plane. Fil: Brito, Gastón. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar GRAFO THINNESS INTERVALO BOXICITY INTERSECCION BANDWIDTH SMT Z3 GRAPH THINNESS INTERVAL BOXICITY INTERSECTION BANDWIDTH SMT Z3 Sobre la thinness en un grafo On the thinness of a graph info:eu-repo/semantics/bachelorThesis info:ar-repo/semantics/tesis de grado info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000574_Brito_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
language	Español
orig_language_str_mv	spa
topic	GRAFO THINNESS INTERVALO BOXICITY INTERSECCION BANDWIDTH SMT Z3 GRAPH THINNESS INTERVAL BOXICITY INTERSECTION BANDWIDTH SMT Z3
spellingShingle	GRAFO THINNESS INTERVALO BOXICITY INTERSECCION BANDWIDTH SMT Z3 GRAPH THINNESS INTERVAL BOXICITY INTERSECTION BANDWIDTH SMT Z3 Brito, Gastón Sobre la thinness en un grafo
topic_facet	GRAFO THINNESS INTERVALO BOXICITY INTERSECCION BANDWIDTH SMT Z3 GRAPH THINNESS INTERVAL BOXICITY INTERSECTION BANDWIDTH SMT Z3
description	La thinness de un grafo, definida inicialmente en 2007, es un invariante que generaliza a los grafos de intervalos. Todo grafo tiene un valor numérico de thinness y los grafos con thinness 1 coinciden con los grafos de intervalos. Un grafo es k-thin si sus vértices pueden ordenarse de manera que exista una partición de los v´ertices en k clases cumpliendo que para cada tripla de vértices r < s < t si r y s pertenecen a la misma clase y existe una arista entre r y t, entonces existe una arista entre s y t. La thinness es el menor valor de k tal que el grafo sea k-thin. En este trabajo definimos un modelo de intersección para los grafos con thinness y thinness propia menor o igual a 2 restringiendo los grafos con boxicity 2. Se caracterizan los grafos k-thin y k-thin propios utilizando propiedades de la matriz de adyacencia. Se acota la thinness en relación al bandwidth de un grafo y se hace un resumen de las relaciones conocidas. Se calcula la thinness utilizando SAT Module Theory (SMT), tanto para determinar si vale la propiedad k-thin como para obtener el valor de la thinness mediante optimización. Se evalúa la performance sobre familias de grafos con los resolvedores Z3 Theorem Solver y OptiMathSat. Adicionalmente se utilizan las mismas técnicas para calcular una representación como una intersección de rectángulos en el plano.
author2	Bonomo, Flavia
author_facet	Bonomo, Flavia Brito, Gastón
format	Tesis de grado Tesis de grado publishedVersion
author	Brito, Gastón
author_sort	Brito, Gastón
title	Sobre la thinness en un grafo
title_short	Sobre la thinness en un grafo
title_full	Sobre la thinness en un grafo
title_fullStr	Sobre la thinness en un grafo
title_full_unstemmed	Sobre la thinness en un grafo
title_sort	sobre la thinness en un grafo
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2020
url	https://hdl.handle.net/20.500.12110/seminario_nCOM000574_Brito https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesisg&d=seminario_nCOM000574_Brito_oai
work_keys_str_mv	AT britogaston sobrelathinnessenungrafo AT britogaston onthethinnessofagraph
_version_	1843126915995533312

Sobre la thinness en un grafo

Ejemplares similares