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

Vista sencilla de ítem
dc.contributor.advisorChalermsook, Parinya
dc.contributor.coadvisorTorres , Pablo
dc.creatorCapretto, Margarita
dc.date.accessioned2022-05-24T21:21:03Z
dc.date.available2022-05-24T21:21:03Z
dc.date.issued2021-03-10
dc.description.abstractEn 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.es
dc.description.peerreviewedPeer reviewed
dc.formatapplication/pdf
dc.identifier.urihttp://hdl.handle.net/2133/23731
dc.language.isospaes
dc.publisherFacultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosarioes
dc.rightsopenAccesses
dc.rights.holderCapretto, Margaritaes
dc.rights.textReconocimiento - Compartir igual (by-sa): Se permite el uso comercial de LA OBRA y de las posibles obras derivadas, la distribución de las cuales se debe hacer con una licencia igual a la que regula LA OBRA original.es
dc.rights.urihttp://creativecommons.org/licenses/by/2.5/ar/*
dc.subjectTeoría de grafoses
dc.subjectGrafos rectánguloses
dc.subjectConjunto de golpees
dc.subjectMatemática aplicadaes
dc.subjectBrecha de dualidades
dc.subjectNúmero de Ramseyes
dc.titleBrecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectánguloes
dc.typebachelorThesis
dc.typeTésis de Grado
dc.type.collectiontesis
dc.type.otherbachelorThesises

Archivos

Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
Tesina de Licenciatura en Ciencias de la Computación. Capretto, Margarita.pdf
Tamaño:
634.98 KB
Formato:
Adobe Portable Document Format
Descripción:
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
Nombre:
license.txt
Tamaño:
3.59 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar

Colecciones

FCEIA-ECEN-DCC- Trabajos Finales de Grado (trabajos finales, proyectos y tesinas)