Some contributions from graph theory to the design and study of large and fault-tolerant interconnection networks

Autor: Pelayo Melero, Ignacio Manuel
Jazyk: angličtina
Rok vydání: 2000
Předmět:
Zdroj: TDX (Tesis Doctorals en Xarxa).
Druh dokumentu: Doctoral Thesis
Popis: Esta tesis trata diversas cuestiones relacionadas con el diseño y estudio de redes de interconexión densas y fiables. Concretamente en ella se han incluido cuatro grupos de contribuciones. En primer lugar se presenta una nueva lista de grafos densos de diámetro seis. Cada uno de estos grafos se ha diseñado mediante un tipo particular de composición a partir de losgrafos biapartitos de Moore de diamétro seis con una familia de grafos completos. Se presentan nuevos grafos obtenidos hasta grado máximo 14, aunque el método utilizado permite teóricamente producir grafos densos de diámetro seis y grado máximo una potencia de un número primo menos uno. A continuación, se lleva a cabo una reformulación de los grafos compuestosgeneralizados a partir de la cual se aborda el problema de su 1-vértice vulnerabilidad del diamétro, obteniéndose que, en general, esta es quasi-óptima.En tercer lugar, se lleva a cabo un análisis sobre conectividad y superconectavididad bajo condiciones sobre el diámetro y sobre el orden de la familia de p-ciclos generalizados, utilizando la terminología de Hamidoune. Finalmente, exponen una serie de resultados sobre conectividad, superconectividad y extraconectividad bajo condiciones sobre el diámetro, a partir de la introducción de un único método de demostración constructiva denominado algoritmo de retirada progresiva y de una nueva familia de parámetros definida partiendo de la del parámetro 1 de Fiol y Fábrega.
Databáze: Networked Digital Library of Theses & Dissertations