Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme
Universitšt Oldenburg   

Publications: Details


Document Description

Author: Günther Stiege
Title: Standard Decomposition and Periodicity of Digraphs
Kind of Publication: Report. Berichte aus dem Fachbereich Informatik 05/01, Universität Oldenburg, November 2001
Date: November 2001
Institution: Universitšt Oldenburg; Abteilung Betriebssysteme und Verteilte Systeme
Pages, Language 16, English
Keywords: digraph decomposition, periodicity of digraphs
CR Classification: E.1[Data Structures]: Graphs and networks; G.2.2 [Graph Theory];
General Terms (ACM): Theory, Algorithms
up

Abstract

The usual decomposition of digraphs into weak and strong components is too coarse. Applying methods from undirected graphs, the strong components of a digraph are further decomposed into peripheral s-trees, stopfree s-kernels, internal s-trees, s-subcomponents, and s-biblocks. The latter in turn are subdivided into periodicity classes. A new algorithm of complexity O(m+n) for finding the periods is presented. A graphical representation of the standard decomposition of a digraph is outlined.

Kurzfassung

Die übliche Zerlegung von Digraphen in schwache und starke Zusammenhangskomponenten ist zu grob. Mit Methoden zur Zerlegung ungerichteter Graphen lassen sich die starken Zusammenhangskomponenten von Digraphen unterteilen in periphere s-Bäume, stoppfreie s-Kerne, interne s-Bäume, s-Subkomponenten und s-Biblöcke. Letztere wiederum werden in Periodizitätsklassen unterteilt. Es wird ein neuer Algorithmus zur Bestimmung der Perioden vorgestellt. Eine graphische Darstellung der Standardzerlegung von Digraphen wird umrissen.

up

Download

up

Remarks

None.
up


Last change: Oct 04 2002 stiege