zbMATH — the first resource for mathematics

Local and variable neighborhood search for the \(k\) -cardinality subgraph problem. (English) Zbl 1211.90298
Summary: The minimum weighted \(k\)-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly \(k\) edges whose sum of weights is minimum. For this \(NP\)-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.

90C59 Approximation methods and heuristics in mathematical programming
90C35 Programming involving graphs or networks
Full Text: DOI
[1] Baum, B.E.: Toward practical ’neural’ computation for combinatorial optimization problems. In: Deker, J. (ed.) Neural Networks for Computing. American Institute of Physics, New York (1986)
[2] Blum, C., Ehrgott, M.: Local search algorithms for the k-cardinality tree problem. Discrete Appl. Math. 128(2-3), 511–540 (2003) · Zbl 1038.90085 · doi:10.1016/S0166-218X(02)00548-6
[3] Ehrgott, M.: Optimization problems in graphs under cardinality restrictions (in German). Master’s thesis, University of Kaiserslautern, Department of Mathematics (1992)
[4] Ehrgott, M., Freitag, J.: K_TREE/K_SUBGRAPH: a program package for minimum weighted K-cardinality trees and subgraphs. Eur. J. Oper. Res. 93(1), 224–225 (1996) · Zbl 0925.90368 · doi:10.1016/0377-2217(96)00084-7
[5] Fischetti, M., Hamacher, H., Jörnsten, K., Maffioli, F.: Weighted k-cardinality trees: complexity and polyhedral structure. Networks 24, 11–21 (1994) · Zbl 0809.90124 · doi:10.1002/net.3230240103
[6] Hansen, P., Mladenović, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001) · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[7] Hansen, P., Mladenović, N.: Variable neighborhood search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics. Kluwer Academic, New York (2003) · Zbl 1102.90371
[8] Jörnsten, K., Lokketangen, A.: Tabu search for weighted k-cardinality trees. Asia Pac. J. Oper. Res. 14(2), 9–26 (1997) · Zbl 0909.90265
[9] Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997) · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[10] Mladenović, N., Urošević, D.: Variable neighborhood search for the k-cardinality tree. In: Resende, M.G.C., de Sousa, J.P. (eds.) Metaheuristics: Computer Decision-Making. Kluwer Academic, Dordrecht (2003)
[11] Prim, R.C.: Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36 (1957)
[12] Urošević, D., Brimberg, J., Mladenović, N.: Variable neighborhood decomposition search for the edge weighted k-cardinality tree problem. Comput. Oper. Res. 31, 1205–1213 (2004) · Zbl 1068.68108 · doi:10.1016/S0305-0548(03)00073-X
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.