Variable neighborhood search for the heaviest k-subgraph

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

doi:10.1016/j.cor.2008.12.020

Variable neighborhood search for the heaviest k-subgraph

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

Research output: Journal article publication › Journal article › Academic research › peer-review

54 Citations (Scopus)

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.

Original language	English
Pages (from-to)	2885-2891
Number of pages	7
Journal	Computers and Operations Research
Volume	36
Issue number	11
DOIs	https://doi.org/10.1016/j.cor.2008.12.020
Publication status	Published - 1 Nov 2009

Keywords

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

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

More information

10.1016/j.cor.2008.12.020

Cite this

@article{4015d7a1844b4ff3978b09dd55ee1cf4,

title = "Variable neighborhood search for the heaviest k-subgraph",

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",

author = "Jack Brimberg and Nenad Mladenovi{\'c} and Dragan Uro{\v s}evi{\'c} and Ngai, \{Wai Ting\}",

year = "2009",

month = nov,

day = "1",

doi = "10.1016/j.cor.2008.12.020",

language = "English",

volume = "36",

pages = "2885--2891",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "11",

}

TY - JOUR

T1 - Variable neighborhood search for the heaviest k-subgraph

AU - Brimberg, Jack

AU - Mladenović, Nenad

AU - Urošević, Dragan

AU - Ngai, Wai Ting

PY - 2009/11/1

Y1 - 2009/11/1

N2 - 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.

AB - 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.

KW - Combinatorial optimization

KW - Heaviest k-subgraph

KW - Maximum diversity

KW - Metaheuristics

KW - Variable neighborhood search

UR - http://www.scopus.com/inward/record.url?scp=64849113019&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2008.12.020

DO - 10.1016/j.cor.2008.12.020

M3 - Journal article

SN - 0305-0548

VL - 36

SP - 2885

EP - 2891

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 11

ER -

Variable neighborhood search for the heaviest k-subgraph

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this