Alianzas en grafos

Labory Pesquer, Gloria (2018). Alianzas en grafos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Alianzas en grafos
Autor/es:
  • Labory Pesquer, Gloria
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 2018
Materias:
Palabras Clave Informales: Alianza; grafos soles; Grafos orugas; Dominación; Alliance; Sun graphs; Caterpillar graphs; Domination.
Escuela: E.T.S. de Ingenieros Informáticos (UPM)
Departamento: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
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 (296kB) | Vista Previa

Resumen

En la práctica, una alianza puede ser un vínculo o una conexión entre individuos, familias, estados, entidades, etc. Formalmente, un conjunto no vacío S de vértices de un grafo G es una alianza defensiva si cada vértice de S tiene al menos uno o más vecinos en S que fuera de él. Durante la pasada década hubo un desarrollo notable de tres tipos de alianzas, alianzas defensivas, alianzas ofensivas y alianzas duales. Debido a la variedad de aplicaciones, las alianzas han recibido una especial atención por muchos científicos e investigadores. Hay aplicaciones de alianzas en varias áreas como la bioinformática, la computación distribuida, las comunidades web, las redes sociales, la clasificación de los datos, empresas, etc. Distintos parámetros de alianza han sido de nidos y un gran número de resultados teóricos (algorítmicos y computacionales) se han obtenido para varios tipos de grafos. En este documento se presenta un survey de los resultados obtenidos hasta ahora sobre las alianzas, centrándonos principalmente en las alianzas defensivas. Además, se dan algunos resultados y algoritmos sobre parámetros de alianzas defensivas para dos tipos de grafos, grafos soles y grafos orugas.---ABSTRACT---In practice, an alliance can be a bond or connection between individuals, families, states, or entities, etc. Formally, a non-empty set S of vertices of a graph G is a defensive alliance if every vertex of S has at least one more neighbour inside of S than it has outside of S. During the last decade there has been a remarkable development on three kinds of alliances, defensive alliance, o ensive alliance and powerful alliance. Due to their variety of applications, the alliances have received a special attention from many scientists and researchers. There are applications of alliances in several areas such as bioinformatics, distributed computing, web communities, social networks, data clustering, business, etc. Several alliance numbers have been de ned and a huge number of theoretical (algorithmic and computational) results are obtained for various graph classes. In this paper, we present a survey with the results obtein about alliances, mainly in the defensive alliances. Also, we give some results and algorithms about alliance numbers for two graph classes, sun graphs and caterpillar graph

Más información

ID de Registro: 51662
Identificador DC: http://oa.upm.es/51662/
Identificador OAI: oai:oa.upm.es:51662
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 17 Jul 2018 07:39
Ultima Modificación: 17 Jul 2018 07:39
  • GEO_UP4
  • 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
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM