Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Günther Stiege
Title: Edge Partitions in Undirected Graphs
Kind of Publication: Report. Berichte aus dem Fachbereich Informatik 05/98, Universität Oldenburg, September 1998
Date: September 1998
Institution: Universität Oldenburg; Abteilung Betriebssysteme und Verteilte Systeme
Pages, Language 35, English
Keywords: Edge partition, Menger's Theorem
CR Classification: E.1 [Data Structures]: Graphs; G.2.2 [Graph Theory]: Path and circuit problems
General Terms (ACM): Theory
up

Abstract

Partitions of the set of edges of an undirected graph are investigated in general. The set of vertices of attachment of a partition and the partition of the W-components of a set of vertices are defined. Their properties show a high degree of duality. An algorithm to find the W-components is presented. The results are applied to a proof of Menger's theorem combined with an algorithm for finding maximal sets of vertex-disjoint paths as well as minimal sets of separating vertices.

Kurzfassung

Es werden allgemeine Kantenpartitionen ungerichteter Graphen untersucht. Dazu werden die Verheftungspunkte einer Partition und die Partition der W-Komponenten einer Knotenmenge eingeführt. Ihre Eigenschaften weisen ein hohes Maß an Dualität auf. Es wird ein Algorithmus zum Auffinden der W-Komponenten vorgestellt. Die Ergebnisse werden zum Beweis des Mengerschen Satzes benutzt. Zusammen mit dem Beweis wird ein Algorithmus angegeben, der eine maximale Menge knotendisjunkter Pfade sowie eine minimale Menge trennender Knoten findet.
up

Download

up

Remarks

None.
up


Last change: Oct 7, 1998 stiege