OPUS


Modelle für die Informationsausbreitung in Graphen

  • In dieser Arbeit werden Übergangswahrscheinlichkeiten für die anderen beiden Modelle abgeleitet. Des weiteren wird gezeigt, dass sich die Anzahl der benötigten Gleichungen zum Lösen der in [21] angegebenen Rekursion für die mittleren Erstankunftszeiten der den Modellen zugrunde liegenden Markovketten für den Sterngraphen zu 2 j V j 1 ergibt. Es wird für bestimmte Graphen mit guten Symmetrieeigenschaften eine alternative Darstellung als Markovkette angegeben. Für eben diese Graphen werden nur O (j V j) viele Gleichungen benötigt, um eine äquivalente Rekursion für die mittlere Zeit bis zum Informieren von ganz V zu lösen. Es werden Reduktionen und Schranken für die mittleren Erstankunftszeiten angegeben und unabhängig von [9] und [7] wird eine Variante des Push-Algorithmus mit Gedächtnis eingeführt, für welche eine obere Schranke für die Laufzeit angegeben wird. Allem vorangestellt wird kurz das zugrunde liegende Problem und vor allem der Push-Algorithmus beleuchtet und es werden wichtige frühere Ergebnisse anderer Autoren vorgestellt. Abschließend werden die Ergebnisse bewertet und offene Probleme angegeben. Es werden in dieser Arbeit nicht behandelte Modelle vorgeschlagen.

Download full text files

  • application/pdf MA_Alrik_Messner_korrigierte_Fassung.pdf (378 KB) deu

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Alrik Messner
Document Type:Master's Thesis
Language:German
Year of Completion:2015
Granting Institution:Hochschule Mittweida
Release Date:2016/01/07
GND Keyword:Graphen
Institutes:03 Mathematik / Naturwissenschaften / Informatik
Access Rights:Innerhalb der Hochschule
Licence (German):License LogoEs gilt das UrhG

$Rev: 13581 $