Fachbereich
    Informatik  Abteilung 
Betriebssysteme und Verteilte Systeme
Universität Oldenburg   

Research Areas & Projects


Periodicity in Digraphs

Responsible:  Stiege   Project Status:  dormant
up

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.

Literature:
Student Theses:
up


Last change: Apr 26 2000 stiege