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