Logo der Fakultät Logo LG Theoretische Informatik
 

Abschlussarbeit

Illustration

Ausbalancieren von gewichteten Pfad-Dekompositionen von Ternären Bäumen

Status: in Bearbeitung
Beschreibung: Die "Heavy Path Decomposition" ist eine bekannte Technik aus der Datenstrukturanalyse, die es erlaubt einen unbalancierten Baum in eine balancierte Hierarchie von Pfaden aufzuteilen. Wir betrachten Bäume in deren Blättern ganzzahlige Gewichte gespeichert sind. Die inneren Knoten enthalten das aggregierte Gewicht ihrer Kinder. Ziel ist es eine ternären Baum so zu gewichten, dass die Gewichte der zwei Kinder mit dem kleinerem Gewicht gleich groß sind. Es ist bereits eine Technik bekannt, wie man dies erreichen kann. Das Gesamtgewicht des Baumes wächst dabei kubisch. In der Arbeit soll eine Verbesserung dieser Technik erforscht werden. Außerdem sollen kleine Instanzen dieses Problems optimal gelöst werden. Die Fragestellung findet Anwendung bei einem Algorithmus zur Realiserung von Polyedern auf dem Gittern. Eine Verbesserung beim Ausbalancieren würde auch die Qualität dieses Algorithmus verbessern.
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen