Article ID Journal Published Year Pages File Type
475851 Computers & Operations Research 2009 7 Pages PDF
Abstract

This paper presents a variable neighborhood search (VNS) heuristic for solving the heaviest kk-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.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , , ,