Proyecto fin de carrera

Recubrimiento por vertices y dominacion: Algoritmos sobre grafos de proximidad y grafos aleatorios    Ir arriba

Título:  Recubrimiento por vértices y dominación: Algoritmos sobre grafos de proximidad y grafos aleatorios
Autor:  Jose Luis Capilla Lara
Tutor:  Gregorio Hernández Peñalver
Fecha:  Julio 2012

 

Introduccion

Recubrimiento por vertices y dominacion: Algoritmos sobre grafos de proximidad y grafos aleatorios    Ir arriba

En el mundo cotidiano existen infinidad de problemas.

Muchos de ellos no llegan a ser modelados ni implementados de modo computacional dada la complejidad de tiempo y/o espacio que representarían sus posibles soluciones.

En Teoría de Complejidad se clasifican los problemas a tratar y también se estudia que tan fácil o rápido se pueden resolver.

La clase NP-Completo agrupa una serie de problemas de gran complejidad que debido a sus características pueden reducirse a problemas que se puedan solucionar en tiempo polinómico.

El objetivo de este proyecto es poder realizar un análisis completo de uno de los principales problemas de la clase NP-Completo: El Problema de Recubrimiento por Vértices.

Concretamente nos centraremos en:

  • Problemas de Recubrimiento de Vértices
  • Problemas de Dominación de Vértices

Para encontrar soluciones rápidas próximas a las soluciones óptimas de este tipo de problemas se han implementado una serie de algoritmos aproximados que siguen distintos enfoques.

Se ha desarrollado una aplicación de escritorio en Java que permite aplicar los distintos algoritmos de recubrimiento implementados sobre un conjunto de grafos extenso:

  • Grafos de Proximidad
  • Mallas
  • Grafos creados aleatoriamente
  • Grafos creados manualmente

Los problemas de Recubrimiento de Vértices los podemos encontrar en la vida real en distintos campos: bioinformática, ingeniería civil, comunicaciones

Concretamente se suelen utilizar en problemas de vigilancia:

  • El conjunto de cámaras necesarias para cubrir una serie de calles compone un conjunto recubrimiento

Los problemas de dominación los encontramos principalmente en el campo de la comunicación entre elementos de las redes adhoc.

Los conjuntos dominantes conexos se utilizan para obtener buenos caminos en redes móviles:

  • Las redes móviles ad hoc son redes donde los nodos se pueden mover de forma libre y no dependen de un control central establecido.
  • Este tipo de redes son especialmente útiles en escenarios que requieren de estrategias rápidas y eficientes de comunicación como son las operaciones militares o las operaciones de rescate en caso por ejemplo de incendios, terremotos o inundaciones. También se pueden emplear para extender la cobertura de las redes inalámbricas actuales.