Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
Solving the Euclidean Bounded Diameter Minimum Spanning Tree Problem by Clustering–Based (Meta–)Heuristics
verfasst von : Martin Gruber, Günther R. Raidl
Erschienen in: Computer Aided Systems Theory - EUROCAST 2009
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The bounded diameter minimum spanning tree problem is an
$\mathcal{NP}$
-hard combinatorial optimization problem arising in particular in network design. There exist various exact and metaheuristic approaches addressing this problem, whereas fast construction heuristics are primarily based on Prim’s minimum spanning tree algorithm and fail to produce reasonable solutions in particular on large Euclidean instances.
In this work we present a method based on hierarchical clustering to guide the construction process of a diameter constrained tree. Solutions obtained are further refined using a greedy randomized adaptive search procedure. Especially on large Euclidean instances with a tight diameter bound the results are excellent. In this case the solution quality can also compete with that of a leading metaheuristic.