Titelaufnahme

Titel
Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem / Martin Gruber
VerfasserGruber, Martin
Begutachter / BegutachterinRaidl, Günther ; Pferschy, Ulrich
Erschienen2009
UmfangXIV, 156 S. : Ill., graph. Darst.
HochschulschriftWien, Techn. Univ., Diss., 2009
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)kombinatorische Optimierung / Netzwerkdesign / durchmesserbeschränkter minimaler Spannbaum / ganzzahlig lineare Programmierung / Branch&Cut / Metaheuristiken / evolutionäre Algorithmen / Ameisensysteme / variable Nachbarschaftssuche
Schlagwörter (EN)combinatorial optimization / network design / bounded diameter minimum spanning tree / integer linear programming / branch-and-cut / metaheuristics / evolutionary algorithms / ant colony optimization / variable neighborhood search
Schlagwörter (GND)Spannender Baum / Minimaler Graph / Kombinatorische Optimierung / Ganzzahlige lineare Optimierung / Metaheuristik
URNurn:nbn:at:at-ubtuw:1-24552 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem [1.22 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

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 <