Name
Abstract | ||
|---|---|---|
Given an undirected graph with costs associated to its edges and pairs of edges, the Quadratic Minimum Spanning Tree Problem (QMSTP) requires to determine a spanning tree of minimum total cost. This is a proper model for network problems in which both routing and interference costs need to be considered. It is NP-hard in the strong sense and not approximable unless P=NP. This paper describes a Tabu Search algorithm, with two independent and adaptively tuned tabu lists, and a Variable Neighbourhood Search algorithm. Both metaheuristics are based on the same neighbourhood, but the Tabu Search proves more effective and robust than the Variable Neighbourhood Search. To assess the quality of these results, we provide a comparison with the heuristic algorithms proposed in the recent literature and we reimplement, with minor improvements, an exact algorithm drawn from the literature, which confirms the optimality of the results obtained on small instances. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.amc.2012.05.043 | Applied Mathematics and Computation |
Keywords | Field | DocType |
Quadratic Minimum Spanning Tree Problem,Binary quadratic programming,Tabu Search,Variable Neighbourhood Search,Branch-and-bound | Mathematical optimization,Search algorithm,Distributed minimum spanning tree,Guided Local Search,Spanning tree,Tabu search,Kruskal's algorithm,Mathematics,Reverse-delete algorithm,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
218 | 23 | 0096-3003 |
Citations | PageRank | References |
17 | 1.08 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Roberto Cordone | 1 | 310 | 28.87 |
| Gianluca Passeri | 2 | 19 | 1.58 |