Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Günther Stiege and Ingo Stierand
Title: Connectedness-Based Hierarchical Decomposition of Undirected Graphs
Kind of Publication: Report. Berichte aus dem Department für Informatik 03/03, Universität Oldenburg, August 2003
Date: August 2003
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 22, English
Keywords: Graph decomposition
CR Classification: E.1 [Data Structures]: Graphs and Networks; G2.2 [Graph Theory];
General Terms (ACM): Theory, Algorithms
up

Abstract

For k>=0, undirected graphs can be decomposed into maximal (by subgraph ordering) k-connected subgraphs, called k-components. They can also be decomposed into maximal k-edgeconnected subgraphs, called k-edgecomponents. Algorithms for finding these components are presented. Heuristics which we call RGB (red/green/blue) are used to improve performance.

Kurzfassung

Ungerichtete Graphen lassen sich in k-Komponenten (k>=0) zerlegen. Das sind maximale k-zusammenhängende Untergraphen (in bezug auf die partielle Ordnung von Untergraphen). Ungerichtete Graphen lassen sich auch in maximale k-kantenzusammenhängende Untergraphen, genannt k-Kantenkomponenten, zerlegen. Wir stellen Algorithmen zur Bestimmung dieser Zerlegungen vor. Zur Verbesserung der Effizienz dieser Zerlegungen werden Heuristiken, die wir RGB (red/green/blue) nennen,eingesetzt.

up

Download

up

Remarks

None.
up



Last change: 2006/02/26 (Stiege)