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.

Description

Title: GTapp: dominating sets within triangulations
Author/s:
  • Moreno Cervera, Héctor
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2016
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

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.

More information

Item ID: 42885
DC Identifier: http://oa.upm.es/42885/
OAI Identifier: oai:oa.upm.es:42885
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 18 Jul 2016 10:35
Last Modified: 27 Oct 2016 07:49
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM