Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Günther Stiege
Title: An Algorithm for Finding the Connectivity Structure of Undirected Graphs
Kind of Publication: Report. Hildesheimer Informatik-Berichte 13/97, Universität Hildesheim, May 1997
Date: May 1997
Institution: Universität Hildesheim; Institut für Betriebssysteme und Rechnerverbund
Pages, Language 16, English
Keywords: Connectivity, graph decomposition
CR Classification: E.1 [Data Structures]: Graphs; G.2.2 [Graph Theory]: Graph algorithms
General Terms (ACM): Algorithms, Theory
up

Abstract

An algorithm is presented which decomposes an undirected graph into a hierarchy of components: Connected components, peripheral trees, stopfree kernels, internal trees, subcomponents, and biblocks. The algoritm consists of a simple "token moving" procedure to identify the peripheral trees and a procedure based on depth-first search to find the stopfree kernels and their internal structure. All together, the complexity is O(m), m being the number of edges, if there are at least as many edges as vertices.

Kurzfassung

Es wird ein Algorithmus vorgestellt, der einen ungerichteten Graphen in eine Hierarchie von Komponenten zerlegt: Zusammenhangskomponenten, periphere Bäume, stoppfreie Kerne, interne Bäume, Subkomponenten und Biblöcke. Zum Finden der peripheren Bäume wird eine Prozedur benutzt, die Marken bewegt. Mittels Tiefensuche werden die stoppfreien Kerne und deren interne Struktur gefunden. Die Gesamtkomplexität in Graphen, die nicht weniger Kanten als Knoten haben, ist O(m), wobei m die Kantenzahl ist.
up

Download

up

Remarks

None.
up


Last change: Oct 7, 1998 stiege