Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo

En teoría de grafos, el problema de encontrar el conjunto independiente máximo (MIS, por sus siglas en inglés), y el problema de encontrar el conjunto de golpe mínimo (MHS), son de vital relevancia en el campo de estudi. En cuanto a la complejidad computacional, ambos son NP difíciles (incluso de ap...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Capretto, Margarita
Otros Autores: Chalermsook, Parinya
Formato: bachelorThesis Tésis de Grado
Lenguaje:Español
Publicado: Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario 2022
Materias:
Teoría de grafos
Grafos rectángulos
Conjunto de golpe
Matemática aplicada
Brecha de dualidad
Número de Ramsey
Acceso en línea:http://hdl.handle.net/2133/23731
http://hdl.handle.net/2133/23731
Aporte de:
Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario
id I15-R121-2133-23731
record_format dspace
institution Universidad Nacional de Rosario
institution_str I-15
repository_str R-121
collection Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR)
language Español
orig_language_str_mv spa
topic Teoría de grafos
Grafos rectángulos
Conjunto de golpe
Matemática aplicada
Brecha de dualidad
Número de Ramsey
spellingShingle Teoría de grafos
Grafos rectángulos
Conjunto de golpe
Matemática aplicada
Brecha de dualidad
Número de Ramsey
Capretto, Margarita
Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
topic_facet Teoría de grafos
Grafos rectángulos
Conjunto de golpe
Matemática aplicada
Brecha de dualidad
Número de Ramsey
description En teoría de grafos, el problema de encontrar el conjunto independiente máximo (MIS, por sus siglas en inglés), y el problema de encontrar el conjunto de golpe mínimo (MHS), son de vital relevancia en el campo de estudi. En cuanto a la complejidad computacional, ambos son NP difíciles (incluso de aproximación) para grafos en general. En esta tesina, nos centramos en las familias de grafos de rectángulos, cuadrados y de ganchos, que son entradas más simples para esta problemática. Estudiamos, asimismo, algunos problemas combinatorios extremales, y analizamos de qué manera pueden utilizarse para obtener algoritmos de aproximación para MIS y MHS en estas clases de grafos.
author2 Chalermsook, Parinya
author_facet Chalermsook, Parinya
Capretto, Margarita
format bachelorThesis
Tésis de Grado
author Capretto, Margarita
author_sort Capretto, Margarita
title Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
title_short Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
title_full Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
title_fullStr Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
title_full_unstemmed Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
title_sort brecha de dualidad y límites de tipo ramsey para familias de grafos de intersección de rectángulo
publisher Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario
publishDate 2022
url http://hdl.handle.net/2133/23731
http://hdl.handle.net/2133/23731
work_keys_str_mv AT caprettomargarita brechadedualidadylimitesdetiporamseyparafamiliasdegrafosdeinterseccionderectangulo
bdutipo_str Repositorios
_version_ 1764820411556560900

Ejemplares similares