Refine
Document Type
- Bachelor Thesis (1)
- Master's Thesis (1)
Language
- German (2)
Keywords
- Graphen (2) (remove)
Institute
- 03 Mathematik / Naturwissenschaften / Informatik (2) (remove)
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.