Authors: Brimberg, Jack
Mladenović, Nenad 
Urošević, Dragan 
Ngai, Eric
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for the heaviest k-subgraph
Journal: Computers and Operations Research
Volume: 36
Issue: 11
First page: 2885
Last page: 2891
Issue Date: 1-Nov-2009
Rank: M21a
ISSN: 0305-0548
DOI: 10.1016/j.cor.2008.12.020
This paper presents a variable neighborhood search (VNS) heuristic for solving the heaviest k-subgraph problem. Different versions of the heuristic are examined including 'skewed' VNS and a combination of a constructive heuristic followed by VNS. Extensive computational experiments are performed on a series of large random graphs as well as several instances of the related maximum diversity problem taken from the literature. The results obtained by VNS were consistently the best over a number of other heuristics tested.
Keywords: Combinatorial optimization | Heaviest k-subgraph | Maximum diversity | Metaheuristics | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on Jun 22, 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.