Universität zu Köln

Dörpinghaus, Jens (2018). Pseudostabile Mengen in Graphen. PhD thesis, Universität zu Köln.

Preview

PDF Main_Druck.pdf - Published Version Download (6MB)

Abstract

Diese Arbeit beschäftigt sich mit der Überdeckung von einfachen Graphenmit pseudostabilen Mengen und der minimalen Zerlegung von Graphen in pseudostabile Mengen. Dabei ist die Wertigkeit einer minimalen Zerlegung des Graphen G = (V, E) durch ζ(G) gegeben. Pseudostabile Mengen stellen eine Verallgemeinerung von stabilen Mengen dar. Pseudostabile Mengen zerfallen in stabile Mengen, erlauben aber unter verschiedenen Nebenbedingungen bestimmte Pfade zwischen diesen. Zur Charakterisierung dieser Pfade wird der darstellende Graph G P einer Zerlegung P des Graphen G = (V, E) in pseudostabile Mengen betrachtet. Dabei führen bestimmte Voraussetzungen zu verschiedenen Unterproble- men, die in dieser Arbeit definiert und untersucht werden. Alle Probleme sind im Allgemeinen N P-vollständig, wie in der vorliegenden Arbeit gezeigt wird. Es werden allerdings auch Graphenklassen beschrieben, auf denen die einzelnen Probleme in polynomieller Zeit lösbar sind. Pseudostabile Mengen erlauben stets nur einen Pfad zwischen stabilen Teilmengen, mehrfach pseudostabile Mengen mehrere Pfade. Die beiden in die- ser Arbeit betrachteten Hauptprobleme sind minPS – eine minimale Zerlegung eines Graphen G in pseudostabile Mengen – und minMPS – eine Zerlegung eines Graphen G in mehrfach pseudostabile Mengen. Eine Zerlegung in pseudostabile Mengen erlaubt nur einen Pfad der Länge 3 zwischen zwei stabilen Mengen. Für den darstellenden Graphen G P gilt, dass er kreisfrei ist und für alle v ∈ V (G P ) gilt, dass δ(v) ∈ {0, 1, 2}. Diese Zerlegung entspricht der optimalen Lösung verschiedener Rangierprobleme auf Güterbahnhöfen. Dies wird in der vorliegenden Arbeit vertieft und es werden von dieser neuen Formulierung aus weitere Lösungsheuristiken und Schranken hergeleitet. Mehrfach pseudostabile Mengen erlauben mehrere Pfade der Länge 3 zwischen stabilen Mengen. Gibt es keine Einschränkungen auf dem darstellenden Graphen G P so ist dies die allgemeinste Fassung des Problems. In dieser Arbeit wird gezeigt, dass dieses Problem eine graphentheoretische Umformulierung des soft Document Clustering ist. Es ist bereits bekannt, dass hard Document Clustering einer Zerlegung eines Dokumentengraphen in stabile Mengen bzw. Cliquen entspricht. Hier wird die Verallgemeinerung auf das weiter gefasste soft Document Clustering diskutiert und es werden Lösungsheuristiken diskutiert. Neben diesen beiden Unterproblemen und den dazugehörigen Anwendungsproblemen werden auch weitere mögliche Verallgemeinerungen, zum Bei-spiel Pseudocliquen, definiert. Eine minimale Zerlegung eines einfachen Graphen G = (V, E) in Pseudocliquen hat dabei die Wertigkeit ζ(G). Diese betten sich nahtlos in die in der vorliegenden Arbeit diskutierten Grundlagen für pseudostabile Mengen ein, da gezeigt wird, dass für den komplementären Graphen G ζ(G) = ζ(G) gilt.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Pseudostable Sets in Graphs English
Translated abstract:	Abstract Language This thesis introduces the covering of simple graphs with pseudostable sets and the minimal partition of a graph in pseudostable sets. The weight of a minimal partition of a graph G = (V, E) is denoted by ζ(G). Pseudostable sets are a generalization of stable sets. They consist of one or two stable sets, but allow to add distinct paths between them. To cha- racterize them and to clarify the conditions, the graph of a set covering G P to a graph partition P of the graph G = (V, E) in pseudostable sets is introduced. Different conditions lead to different subproblems. This thesis shows that all problems are in general N P-complete. But it is possible to show some graph classes for which some problems are computable in polynomial time. Pseudostable sets allow only one path between stable subsets, multiple pseudostable sets allow more than one path. This thesis discusses two sub- problems in detail: minPS – a minimal partition of a graph G in pseudostable sets – and minMPS – a minimal partition of a graph G in multiple pseudostable sets. The problem minPS searches for a minimal set covering P of the graph G = (V, E) with a subset B ⊂ G of blue nodes and edges with pseudostable tuples T where G P is acyclic and δ(v) ∈ {0, 1, 2} for all v ∈ V (G P ). This problem is equivalent to the Train Marshalling Problem covering the rearrangement of cars of an incoming train in a hump yard. This thesis will discuss several novel insights, bounds and heuristics for this problem. The problem minMPS searches for a minimal set covering P of the graph G = (V, E) with a subset B ⊂ G of blue nodes and edges with multiple pseudostable tuples M where G P is acyclic and δ(v) ∈ {0, 1, 2} for all v ∈ V (G P ). If there are no restrictions on the graph G P , this is the most general formulation. It is a graph theoretical reformulation of soft document clustering. Hard document clustering is well known for being solved by a graph partition into stable sets or cliques. Thus this work will discuss the more general formulation with pseudostable sets. Beside these two subproblems and their application this thesis also considers other related topics like pseudocliques. A minimal partition of a simple graph G = (V, E) in pseudocliques has the value ζ(G). We will show that for the complementary graph G ζ(G) = ζ(G) holds. English
Creators:	Creators Email ORCID ORCID Put Code Dörpinghaus, Jens jens.doerpinghaus@scai.fraunhofer.de UNSPECIFIED UNSPECIFIED
Corporate Contributors:	Fraunhofer SCAI
URN:	urn:nbn:de:hbz:38-80669
Date:	2018
Publisher:	Stuttgart: Fraunhofer Verlag
ISBN:	978-3-8396-1327-6
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Graphentheorie, pseudostabile Mengen, Komplexität, Approximation, Heuristik, Transport German Graph theory, pseudostable sets, complexity, approximation, heuristic, transportation English
Date of oral exam:	8 January 2018
Referee:	Name Academic Title Schrader, Rainer Prof. Dr. Randerat, Hubert Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/8066