Pseudostabile Mengen in Graphen

Autori

• Jens Dörpinghaus

Parametri

• Libri di testo
• Libri di testo universitari

Maggiori informazioni sul libro

Diese Arbeit untersucht die Überdeckung einfacher Graphen mit pseudostabilen Mengen und die minimale Zerlegung von Graphen in solche Mengen. Pseudostabile Mengen erweitern das Konzept stabiler Mengen. Bei der Zerlegung pseudostabiler Mengen entstehen stabile Mengen, die jedoch durch bestimmte Pfade verbunden bleiben, unter verschiedenen Nebenbedingungen. Die Arbeit definiert und analysiert verschiedene Unterprobleme, die aus bestimmten Voraussetzungen resultieren, und zeigt, dass alle diese Probleme im Allgemeinen NP-vollständig sind. Gleichzeitig werden Graphenklassen beschrieben, in denen die Probleme in polynomieller Zeit lösbar sind. Ein Anwendungsproblem, das behandelt wird, ist das ›Train Marshalling‹-Problem, bei dem die Zerlegung eines Graphen in pseudostabile Mengen der optimalen Lösung von Rangierproblemen auf Güterbahnhöfen entspricht. Dies wird ausführlich erörtert. Zudem werden neue Lösungsheuristiken und Schranken auf Basis dieser Formulierung abgeleitet. Ein weiteres Anwendungsproblem ist die graphentheoretische Umformulierung des ›Soft Document Clusterings‹. Es wird gezeigt, dass das ›Hard Document Clustering‹ einer Zerlegung eines Dokumenten-Graphen in stabile Mengen oder Cliquen entspricht. Die Arbeit führt die Verallgemeinerung auf das weiter gefasste Soft Document Clustering ein und diskutiert Lösungsheuristiken.

Lingua: Tedesco

Pubblicato: 2018