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.

Description

Title: Alianzas en grafos
Author/s:
  • Labory Pesquer, Gloria
Contributor/s:
  • Hernández Peñalver, Gregorio
Item Type: Final Project
Degree: Grado en Matemáticas e Informática
Date: June 2018
Subjects:
Freetext Keywords: Alianza; grafos soles; Grafos orugas; Dominación; Alliance; Sun graphs; Caterpillar graphs; Domination.
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
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 (296kB) | Preview

Abstract

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

More information

Item ID: 51662
DC Identifier: http://oa.upm.es/51662/
OAI Identifier: oai:oa.upm.es:51662
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 17 Jul 2018 07:39
Last Modified: 17 Jul 2018 07:39
  • 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