GTapp: dominating sets within triangulations

Moreno Cervera, Héctor (2016). GTapp: dominating sets within triangulations. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: GTapp: dominating sets within triangulations
Autor/es:
  • Moreno Cervera, Héctor
Director/es:
  • Hernández Peñalver, Gregorio
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2016
Materias:
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

El incontrolado desarrollo de las ciencias de la computación en las últimas décadas ha provocado que actualmente se generen millones de bytes de contenido cada minuto a lo largo del globo. Es por esto que la teoría de grafos, rama dentro de las matemáticas discretas, cobra cada vez más importancia dentro de las ciencias de la información. Esta teoría no solo nos permite modelar grafos, sino que tambien permite obtener información a partir de redes de nodos. La confluencia de las matemáticas con la informática en este ámbito es lo que hace tan atractivo este proyecto como trabajo de fin de grado. A lo largo de la presente memoria estudiaremos las triangulaciones de grafos, comúnmente utilizadas con el objetivo de modelizar redes inalámbricas, y los conjuntos dominantes, que proporcionan conjuntos de vértices característicos. Este estudio está orientado bajo un punto de vista experimental, donde buscamos obtener resultados a partir datos estadísticos gracias a muestras aleatorias de vértices. Con el fin de conseguir dichas muestras, se ha desarrollado una aplicación que permite visualizar grafos y generar datos estadísticos relativos a los conjuntos dominantes y triangulaciones implementadas. Además, se han obtenido resultados que han permitido establecer nuevas cotas experimentales, además de comprender en mejor medida cuan de buenos eran los diferentes algoritmos propuestos.---ABSTRACT---The uncontrolled computer science development over the past decades has lead us to a world where millions of unique bytes of information are being generated every minute. That is the reason behind why graph theory, field which lies within the discrete mathematics, has becomed increasingly significant for information technologies. This theory not only implies modeling graphs, but also allows obtaining information based on connected networks. The confluence between mathematics and computer science in this field is what makes this project attractive as a final degree portfolio. Along this paper we will study graph triangulations, commonly used for modeling wireless networks, and dominating sets, which provide sets of characteristic nodes. This research is oriented under an experimental point of view, where we try to obtain results upon statistical data thanks to randomly distributed node samples. With the purpose of achieving this samples, we have developed an application capable of visualizing graphs and generating statistical data regarding the implemented dominating sets and triangulations. Moreover, acquired results have permitted establishing new experimental boundaries, as well as led us to understand which algorithm performed better among the proposed.

Más información

ID de Registro: 42885
Identificador DC: http://oa.upm.es/42885/
Identificador OAI: oai:oa.upm.es:42885
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Jul 2016 10:35
Ultima Modificación: 27 Oct 2016 07:49
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM