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 | Abstract: | 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
SCOPUSTM
Citations
50
checked on Nov 11, 2024
Page view(s)
18
checked on Nov 11, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.