Variable neighborhood search for the heaviest k-subgraph
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. (C) 2009 Elsevier Ltd. All rights reserved.
variable neighborhood search heaviest k-subgraph maximum diversity combinatorial optimization metaheuristics