<div class="csl-bib-body">
<div class="csl-entry">Gruber, M. (2009). <i>Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem</i> [Dissertation, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-24552</div>
</div>
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 <
de
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
kombinatorische Optimierung
de
dc.subject
Netzwerkdesign
de
dc.subject
durchmesserbeschränkter minimaler Spannbaum
de
dc.subject
ganzzahlig lineare Programmierung
de
dc.subject
Branch&Cut
de
dc.subject
Metaheuristiken
de
dc.subject
evolutionäre Algorithmen
de
dc.subject
Ameisensysteme
de
dc.subject
variable Nachbarschaftssuche
de
dc.subject
combinatorial optimization
en
dc.subject
network design
en
dc.subject
bounded diameter minimum spanning tree
en
dc.subject
integer linear programming
en
dc.subject
branch-and-cut
en
dc.subject
metaheuristics
en
dc.subject
evolutionary algorithms
en
dc.subject
ant colony optimization
en
dc.subject
variable neighborhood search
en
dc.title
Exact and heuristic approaches for solving the bounded diameter minimum spanning tree problem
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Martin Gruber
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Pferschy, Ulrich
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen
-
dc.type.qualificationlevel
Doctoral
-
dc.identifier.libraryid
AC05041069
-
dc.description.numberOfPages
156
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-24552
-
dc.thesistype
Dissertation
de
dc.thesistype
Dissertation
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
tuw.advisor.orcid
0000-0002-3293-177X
-
item.mimetype
application/pdf
-
item.grantfulltext
open
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.openaccessfulltext
Open Access
-
item.openairetype
doctoral thesis
-
item.openairecristype
http://purl.org/coar/resource_type/c_db06
-
crisitem.author.dept
E186 - Institut für Computergraphik und Algorithmen