Variable neighborhood search for the heaviest k-subgraph

Jack Brimberg, Nenad Mladenović, Dragan Urošević, Wai Ting Ngai

Research output: Journal article publicationJournal articleAcademic researchpeer-review

38 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)2885-2891
Number of pages7
JournalComputers and Operations Research
Issue number11
Publication statusPublished - 1 Nov 2009


  • Combinatorial optimization
  • Heaviest k-subgraph
  • Maximum diversity
  • Metaheuristics
  • Variable neighborhood search

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this