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
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 Jun 14, 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.