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
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


checked on Jun 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.