Informatik  Abteilung 
Betriebssysteme und Verteilte Systeme
Universität Oldenburg   

Research Areas & Projects

Periodicity in Digraphs

Responsible:  Stiege   Project Status:  dormant

Project description: Periodicity as known from Markov chain theory is defined for directed graphs and its properties are derived by purely graph theoretic means. To each strong connected components of a digraph are thus attributed a period p and and each strong connected component is decomposed into p periodicity classes. Paths within a strong connected component always pass with each step from one periodicity class to the next returning to the first class after p steps. An algorithm giving the period of each strong connected component of a digraph was presented.

Student Theses:

Last change: Apr 26 2000 stiege