Local and variable neighborhood search for the <Emphasis Type="Italic">k</Emphasis>-cardinality subgraph problem |
| |
Authors: | Jack Brimberg Nenad Mladenović Dragan Urošević |
| |
Institution: | (1) Department of Business Administration, Royal Military College of Canada, Kingston, ON, Canada;(2) School of Mathematics, Brunel University, West London, Uxbridge, London, UB8 3PH, UK;(3) Mathematical Institute, Serbian Academy of Sciences, Belgrade, Serbia and Montenegro |
| |
Abstract: | 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. |
| |
Keywords: | Variable neighborhood search k-subgraph |
本文献已被 SpringerLink 等数据库收录! |
|