zbMATH — the first resource for mathematics

Variable neighborhood search for the heaviest \(k\)-subgraph. (English) Zbl 1162.90540
Summary: 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.

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
Full Text: DOI
[1] Corneil, D.; Perl, Y., Clustering and domination in perfect graphs, Discrete applied mathematics, 9, 27-39, (1984) · Zbl 0581.05053
[2] Mafioli F. Finding a best subtree on the tree. Technical Report 91.041, Politecnico di Milano, Dipartimento di Elettronica, Milano; 1991.
[3] Billionnet, A., Different formulations for solving the heaviest \(k\)-subgraph problem, Information systems and operational research, 43, 3, 171-186, (2005)
[4] Srivastav, A.; Wolf, K., Finding dense subgraphs with semi-definite programming, Lecture notes in computer science, 1444, 181-191, (1998) · Zbl 0911.90340
[5] Kincaid, R., Good solutions to discrete noxious location problems via metaheuristics, Annals of operations research, 40, 265-281, (1992) · Zbl 0782.90061
[6] Erkut, E., The discrete p-dispersion problem, European journal of operational research, 46, 1, 46-80, (1990)
[7] Duarte, A.; Marti, R., Tabu search and GRASP for the maximum diversity problem, European journal of operational research, 178, 1, 71-84, (2007) · Zbl 1109.90081
[8] Macambira, E., An application of tabu search heuristic for the maximum edge-weighted subgraph problem, Annals of operations research, 117, 175-190, (2002) · Zbl 1028.90041
[9] Macambira E, Meneses C. A GRASP algorithm for the maximum edge subgraph problem. Technical Report, Department of Statistics and Computer Science, State University of Ceara, Brazil; 1998.
[10] Weizhong Y. Experimental study of approximation algorithms for the densest \(k\)-subgraph problem. Masters thesis, McMaster University, Canada; 2003.
[11] Billionnet, A.; Roupin, F., A deterministic approximation algorithm for the densest \(k\)-subgraph problem, International journal of operational research, 3, 3, 301-314, (2008) · Zbl 1138.05322
[12] Gallego M, Duarte A, Laguna M, Marti R. Hybrid heuristics for the maximum diversity problem. Computational Optimization and Applications 2009, in press, doi:10.1007/s10589-007-9161-6. · Zbl 1181.90196
[13] Palubeckis, G., Iterated tabu search for the maximum diversity problem, Applied mathematics and computation, 189, 1, 371-383, (2007) · Zbl 1122.65362
[14] Hansen, P.; Mladenović, N., Variable neighborhood search, (), 145-184 · Zbl 1102.90371
[15] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & operations research, 24, 1097-1100, (1997) · Zbl 0889.90119
[16] Hansen P, Jaumard B, Mladenović N, Parreira A. Variable neighborhood search for weighted satisfiability problem. Technical Report, Les Cahiers du GERAD G2000-62, Montréal, Canada; 2000.
[17] Hansen, P.; Mladenović, N., First improvement may be better than best improvement: an empirical study, Discrete applied mathematics, 154, 802-817, (2006) · Zbl 1120.90048
[18] Aringhieri, R.; Cordone, R.; Melzani, Y., Tabu search versus GRASP for the maximum diversity problem, 4or, 6, 1, 45-60, (2008) · Zbl 1135.90381
[19] Silva, G.C.; De Andrade, M.R.Q.; Ochi, L.S.; Martins, S.L.; Plastino, A., New heuristics for the maximum diversity problem, Journal of heuristics, 13, 4, 315-336, (2007)
[20] Ghosh, J.B., Computational aspects of the maximum diversity problem, Operations research letters, 19, 175-181, (1996) · Zbl 0873.90070
[21] Beasley, J.E., Obtaining test problems via Internet, Journal of global optimization, 8, 429-433, (1996) · Zbl 0848.90126
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.