Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem

Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem

0.00 Avg rating0 Votes
Article ID: iaor20043716
Country: United Kingdom
Volume: 31
Issue: 8
Start Page Number: 1205
End Page Number: 1213
Publication Date: Jul 2004
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

The minimum k-cardinality tree problem on graph G consists in finding a subtree of G with exactly k edges whose sum of weights is minimum. A number of heuristic methods have been developed recently to solve this NP-hard problem. In this paper a decomposition approach is developed and implemented within a successive approximation scheme known as variable neighborhood decomposition search. This approach obtains superior results over existing methods, and furthermore, allows larger prblem instances (up to 5000 nodes) to be solved more efficiently.

Reviews

Required fields are marked *. Your email address will not be published.