| Title |
Metaheuristic approaches for the quadratic minimum spanning tree problem |
| Another Title |
Metaeuristiniai metodai kvadratinio minimalaus dengiančiojo medžio uždaviniui spręsti. |
| Authors |
Palubeckis, Gintaras ; Rubliauskas, Dalius ; Targamadzė, Aleksandras |
| Full Text |
|
| Is Part of |
Informacinės technologijos ir valdymas = Information technology and control.. Kaunas : Technologija. 2010, t. 39, Nr. 4, p. 257-268.. ISSN 1392-124X. eISSN 2335-884X |
| Keywords [eng] |
combinatorial optimization ; quadratic minimum spanning tree ; metaheuristics ; simulated annealing ; genetic algorithm ; Tabu search |
| Abstract [eng] |
Given an undirected graph with costs associated both with its edges and unordered pairs of edges, the quadratic minimum spanning tree problem asks to find a spanning tree that minimizes the sum of costs of all edges and pairs of edges in the tree. We present multistart simulated annealing, hybrid genetic and iterated tabu search algorithms for solving this problem. We report on computational experiments that compare these algorithms on random graphs of size up to 50 vertices. The results indicate that the iterated tabu search algorithm is superior to the other two approaches in terms of both solution quality and computation time. |
| Published |
Kaunas : Technologija |
| Type |
Journal article |
| Language |
English |
| Publication date |
2010 |
| CC license |
|
