Abschlussarbeit
Ausbalancieren von gewichteten Pfad-Dekompositionen von Ternären Bäumen
- Status:
- abgeschlossen
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.
