Authors: | Urošević, Dragan Brimberg, Jack Mladenović, Nenad |
Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem | Journal: | Computers and Operations Research | Volume: | 31 | Issue: | 8 | First page: | 1205 | Last page: | 1213 | Issue Date: | 1-Jan-2004 | Rank: | M22 | ISSN: | 0305-0548 | DOI: | 10.1016/S0305-0548(03)00073-X | 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 problem instances (up to 5000 nodes) to be solved more efficiently. |
Publisher: | Elsevier |
Show full item record
SCOPUSTM
Citations
26
checked on Nov 23, 2024
Page view(s)
17
checked on Nov 23, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.