Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem

Abstract

Das Finden eines durchmesserbeschränkten minimale Spannbaumes (BDMST) ist ein kombinatorisches Optimierungsproblem aus dem Bereich des Netzwerkdesigns und hat Anwendungen in verschiedensten Bereichen. So unter anderem beim Entwurf von kabelgebundenen Kommunikationsnetzwerken, sofern gewisse Anforderungen hinsichtlich der Kommunikationsgüte erfüllt werden sollen. Aber auch bei ad-hoc Funknetzwerken oder bei der Datenkomprimierung sowie bei verteilten Mutual Exclusion Algorithmen gilt es immer wieder, einen BDMST zu berechnen. Bei dieser Problemstellung gilt es, in einem ungerichteten, gewichteten und zusammenhängenden Graphen G=(V,E) mit der Knotenmenge V und der Kantenmenge E einen aufspannenden Baum minimaler Kosten zu finden.<br />Zusätzlich muss gelten, dass die Anzahl der Kanten auf jedem Pfad zwischen zwei beliebigen Knoten innerhalb des Baumes kleiner oder gleich einem Durchmesser D ist. Dieses Problem ist für eine Durchmesserbeschränkung von 4 <=D <