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 Sep 27, 2021

Page view(s)

7
checked on Sep 26, 2021

Google ScholarTM

Check

Altmetric

Altmetric


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