Pseudostabile Mengen in Graphen. - Jens Dörpinghaus

Pseudostabile Mengen in Graphen.

Buch | Softcover
179 Seiten
2018
Fraunhofer Verlag
978-3-8396-1327-6 (ISBN)
59,00 inkl. MwSt
  • Titel ist leider vergriffen;
    keine Neuauflage
  • Artikel merken
Diese Arbeit beschäftigt sich mit der Überdeckung einfacher Graphen mit pseudostabilen Mengen und der minimalen Zerlegung von Graphen in eben solche. Pseudostabile Mengen stellen eine Verallgemeinerung von stabilen Mengen dar. Beim Zerfall pseudostabiler Mengen entstehen wiederum stabile Mengen, die jedoch unter verschiedenen Nebenbedingungen über bestimmte Pfade verbunden bleiben. Dabei führen bestimmte Voraussetzungen zu verschiedenen Unterproblemen, die in dieser Arbeit definiert und untersucht werden. Wie hier ebenfalls gezeigt wird, sind alle diese Probleme im Allgemeinen NP-vollständig. Es werden allerdings darüber hinaus auch Graphenklassen beschrieben, auf denen die einzelnen Probleme in polynomieller Zeit lösbar sind. Als ein Anwendungsproblem wird das 'Train Marshalling'-Problem betrachtet: eine Zerlegung eines Graphen in pseudostabile Mengen entspricht der optimalen Lösung verschiedener Rangierprobleme auf Güter-bahnhöfen. Dies wird in der vorliegenden Arbeit vertieft. Des Weiteren werden auf Basis dieser neuen Formulierung weitere Lösungsheuristiken und Schranken hergeleitet. Als weiteres Anwendungsproblem wird eine graphentheoretische Umformulierung des 'Soft Document Clusterings' betrachtet. Es ist bereits bekannt, dass 'Hard Document Clustering' einer Zerlegung eines Dokumenten-graphen in stabile Mengen bzw. Cliquen entspricht. Im Rahmen dieser Arbeit wird die Verallgemeinerung auf das weiter gefasste Soft Document Clustering eingeführt und Lösungsheuristiken diskutiert.
Erscheinungsdatum
Zusatzinfo zahlr. Abb. u. Tab.
Verlagsort Stuttgart
Sprache deutsch
Maße 148 x 210 mm
Themenwelt Mathematik / Informatik Informatik
Mathematik / Informatik Mathematik Graphentheorie
Schlagworte Algorithms & Data Structures • B • discrete mathematic • Diskrete Mathematik • Effiziente Algorithmen • Fraunhofer SCAI • Graphentheorie • Informatiker • Linear Programming • Mathematiker • Modellierung • Optimierung
ISBN-10 3-8396-1327-2 / 3839613272
ISBN-13 978-3-8396-1327-6 / 9783839613276
Zustand Neuware
Haben Sie eine Frage zum Produkt?
Mehr entdecken
aus dem Bereich
Numbers and Counting, Groups, Graphs, Orders and Lattices

von Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger …

Buch | Softcover (2023)
De Gruyter (Verlag)
64,95