Authors: | Brimberg, Jack Mladenović, Nenad Urošević, Dragan |
Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | Local and variable neighborhood search for the k-cardinality subgraph problem | Journal: | Journal of Heuristics | Volume: | 14 | Issue: | 5 | First page: | 501 | Last page: | 517 | Issue Date: | 1-Oct-2008 | Rank: | M22 | ISSN: | 1381-1231 | DOI: | 10.1007/s10732-007-9046-y | Abstract: | The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods. |
Keywords: | k-subgraph | Variable neighborhood search | Publisher: | Springer Link |
Show full item record
SCOPUSTM
Citations
7
checked on Nov 11, 2024
Page view(s)
16
checked on Nov 11, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.