Title: Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem
Language: English
Authors: Gruber, Martin 
Qualification level: Doctoral
Keywords: kombinatorische Optimierung; Netzwerkdesign; durchmesserbeschränkter minimaler Spannbaum; ganzzahlig lineare Programmierung; Branch&Cut; Metaheuristiken; evolutionäre Algorithmen; Ameisensysteme; variable Nachbarschaftssuche
combinatorial optimization; network design; bounded diameter minimum spanning tree; integer linear programming; branch-and-cut; metaheuristics; evolutionary algorithms; ant colony optimization; variable neighborhood search
Advisor: Raidl, Günther
Assisting Advisor: Pferschy, Ulrich 
Issue Date: 2009
Number of Pages: 156
Qualification level: Doctoral
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.
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 <
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-24552
http://hdl.handle.net/20.500.12708/8975
Library ID: AC05041069
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Show full item record

Page view(s)

11
checked on Feb 24, 2021

Download(s)

50
checked on Feb 24, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.