Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475851 | Computers & Operations Research | 2009 | 7 Pages |
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
Jack Brimberg, Nenad Mladenović, Dragan Urošević, Eric Ngai,