Dominación romana en grafos

El Problema de Dominación Romana fue formalizado por Cockayne et al. Allí, se modeliza el problema del emperador Constantino utilizando la Teoría de Grafos. Se sabe que el Problema de Dominación Romana es NP-completo en general. En esta tesina abordaremos el análisis de la complejidad del problema c...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Cornet, María Gracia
Otros Autores: Torres, Pablo
Formato: bachelorThesis Tésis de Grado
Lenguaje:Español
Publicado: 2022
Materias:
Teoría de grafos
Algoritmos
Programación matemática
Acceso en línea:http://hdl.handle.net/2133/23658
http://hdl.handle.net/2133/23658
Aporte de:
Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario
id I15-R121-2133-23658
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
Algoritmos
Programación matemática
spellingShingle Teoría de grafos
Algoritmos
Programación matemática
Cornet, María Gracia
Dominación romana en grafos
topic_facet Teoría de grafos
Algoritmos
Programación matemática
description El Problema de Dominación Romana fue formalizado por Cockayne et al. Allí, se modeliza el problema del emperador Constantino utilizando la Teoría de Grafos. Se sabe que el Problema de Dominación Romana es NP-completo en general. En esta tesina abordaremos el análisis de la complejidad del problema cuando nos restringimos a ciertas familias de grafos. Entre las familias de grafos a estudiar, están aquellas que se pueden definir por tener una cantidad restringida de P4’s en un sentido local. La estrategia de abordaje para el problema es descomponer el grafo en subgrafos más pequeños, mediante ciertas operaciones. Si conocemos el comportamiento del parámetro γR bajo estas operaciones y podemos calcular el valor del parámetro para estos subgrafos mas pequeños, y todo esto lo podemos hacer en tiempo polinomial, entonces podemos recuperar el valor del número de dominación romana en el grafo original. Parte de los resultados presentados en esta tesina fueron presentados en XIII Jornada de Ciencia y Tecnología: Divulgación de la Producción Científica y Tecnológica de la Universidad Nacional de Rosario (2019); y en LXIX Reunión de Comunicaciones Científicas de la Reunión Anual Virtual de la Unión Matemática Argentina (virtUMA 2020).
author2 Torres, Pablo
author_facet Torres, Pablo
Cornet, María Gracia
format bachelorThesis
Tésis de Grado
author Cornet, María Gracia
author_sort Cornet, María Gracia
title Dominación romana en grafos
title_short Dominación romana en grafos
title_full Dominación romana en grafos
title_fullStr Dominación romana en grafos
title_full_unstemmed Dominación romana en grafos
title_sort dominación romana en grafos
publishDate 2022
url http://hdl.handle.net/2133/23658
http://hdl.handle.net/2133/23658
work_keys_str_mv AT cornetmariagracia dominacionromanaengrafos
bdutipo_str Repositorios
_version_ 1764820411491549184

Ejemplares similares