Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme
Universitšt Oldenburg   

Publications: Details


Document Description

Author: Günther Stiege
Title: Higher Decompositions in Undirected Graphs
Kind of Publication: Report. Berichte aus dem Fachbereich Informatik 01/01, Universität Oldenburg, January 2001
Date: January 2001
Institution: Universitšt Oldenburg; Abteilung Betriebssysteme und Verteilte Systeme
Pages, Language 8, English
Keywords: graph decomposition
CR Classification: E.1[Data Structures]: Graphs and networks; G.2.2 [Graph Theory];
General Terms (ACM): Theory, Algorithms
up

Abstract

The standard decomposition of an undirected graph uses 2-connectivity properties and decomposes the graph into acyclic and cyclic connected components. The latter in turn are decomposed into peripheral trees, stopfree kernels, internal trees, subcomponents, and biblocks. As shown in this report, a similar decomposition is possible for k-connectivity (k>2). The graph is decomposed into k-componentsd and k-cocomponents. An algorithm to find these is outlined.

Kurzfassung

Die Standardzerlegung ungerichteter Graphen benutzt 2-Zusammenhang und zerlegt den Graphen in azyklische und zyklische Zusammenhangskomponenten. Letztere werden in periphere Bäume, stoppfreie Kerne, interne Bäume, Subkomponenten und Biblöcke zerlegt. In diesem Bericht wird gezeigt, daß eine analoge Zerlegung auch für k-Zusammenhang (k>2) möglich ist. Der Graph wird in k-Komponenten und k-Cokomponenten zerlegt. Es wird ein Algorithmus skizziert, mit dem sich diese finden lassen.

up

Download

up

Remarks

None.
up


Last change: 2002/09/25 stierand