Bibliographic Metadata

Title
Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem / Martin Gruber
AuthorGruber, Martin
CensorRaidl, Günther ; Pferschy, Ulrich
Published2009
DescriptionXIV, 156 S. : Ill., graph. Darst.
Institutional NoteWien, Techn. Univ., Diss., 2009
Annotation
Zsfassung in dt. Sprache
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)kombinatorische Optimierung / Netzwerkdesign / durchmesserbeschränkter minimaler Spannbaum / ganzzahlig lineare Programmierung / Branch&Cut / Metaheuristiken / evolutionäre Algorithmen / Ameisensysteme / variable Nachbarschaftssuche
Keywords (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
Keywords (GND)Spannender Baum / Minimaler Graph / Kombinatorische Optimierung / Ganzzahlige lineare Optimierung / Metaheuristik
URNurn:nbn:at:at-ubtuw:1-24552 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem [1.22 mb]
Links
Reference
Classification
Abstract (German)

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 <