Betriebssysteme und Verteilte Systeme
|
|
Abteilung Betriebssysteme und Verteilte Systeme |
|
General Informations
Abstract/Kurzfassung
Full text
Remarks
| 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 |
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.
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.
|
Last change: Oct 04 2002 stiege |
