|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
checked on Sep 27, 2021
checked on Sep 26, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.