|
|
|
|
|
General Informations
Abstract/Kurzfassung
Full text
Remarks
| 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 |
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.
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.
|
Last change: 2006/02/26 (Stiege) |
