Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme
Universitšt Oldenburg   

Publications: Details


Document Description

Author: Günther Stiege
Title: Periodicity: An Application of Digraphs to Markov Chains
Kind of Publication: Report. Hildesheimer Informatik-Berichte 24/95, Universität Hildesheim, August 1995
Date: August 1995
Institution: Universität Hildesheim; Institut für Betriebssysteme und Rechnerverbund
Pages, Language 20, English
Keywords: Periodicity, Markov chain
CR Classification: E.1 [Data Structures]: Graphs; G.2.2 [Graph Theory]: Path and circuit problems;
G.3 [ Probability and Statistics]
General Terms (ACM): Algorithms, Theory
up

Abstract

Periodicity as known from Markov chain theory is defined for directed graphs and its properties derived by purely graph theoretic means. An O**3-complexity algorithm using breadth first search to find the period of a finite strongly connected component is presented.

Kurzfassung

Periodizität, wie sie von Markovketten bekannt ist, wird für gerichtete Graphen definiert. Die Eigenschaften werden auf rein graphentheoretische Art hergeleitet. Es wird ein Algorithmus der Komplexität O**3, der Breitensuche benutzt, zur Bestimmung der Periode einer endlichen starken Zusammenhangskomponente vorgestellt.
up

Download

up

Remarks

None.
up


Last change: Apr 2, 1999 stiege