Abteilung
Betriebssysteme und Verteilte Systeme

Publications: Details

General Informations

Abstract/Kurzfassung

Full text

Remarks

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

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.

Download

PostScript, gzip'ed (236 KBytes)

Remarks

None.

Last change: Apr 2, 1999 stiege