Variable neighborhood search for the heaviest \(k\)-subgraph

DOI10.1016/j.cor.2008.12.020zbMath1162.90540OpenAlexW2067583942MaRDI QIDQ1025229

Jack Brimberg, Dragan Urošević, Nenad Mladenović, Eric W. T. Ngai

Publication date: 18 June 2009

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2008.12.020

zbMATH Keywords

combinatorial optimizationmetaheuristicsvariable neighborhood searchmaximum diversityheaviest \(k\)-subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27)

Related Items

Exact approaches for the orderly colored longest path problem: performance comparison ⋮ A review on algorithms for maximum clique problems ⋮ Maxminmin \(p\)-dispersion problem: a variable neighborhood search approach ⋮ A two-phase intensification tabu search algorithm for the maximum min-sum dispersion problem ⋮ A review on discrete diversity and dispersion maximization from an OR perspective ⋮ A two-phase tabu search based evolutionary algorithm for the maximum diversity problem ⋮ Variable neighborhood search for the travelling deliveryman problem ⋮ Memetic self-adaptive evolution strategies applied to the maximum diversity problem ⋮ Solving the maximum min-sum dispersion by alternating formulations of two different problems ⋮ Variable neighbourhood search: methods and applications ⋮ Iterated greedy for the maximum diversity problem ⋮ Construction and improvement algorithms for dispersion problems ⋮ On solving the densestk-subgraph problem on large graphs ⋮ A hybrid metaheuristic method for the maximum diversity problem

Cites Work

• Unnamed Item
• Good solutions to discrete noxious location problems via metaheuristics
• Tabu search and GRASP for the maximum diversity problem
• The discrete p-dispersion problem
• Tabu search versus GRASP for the maximum diversity problem
• Clustering and domination in perfect graphs
• Computational aspects of the maximum diversity problem
• Variable neighborhood search
• An application of tabu search heuristic for the maximum edge-weighted subgraph problem
• Obtaining test problems via Internet
• Iterated tabu search for the maximum diversity problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• First vs. best improvement: an empirical study
• Hybrid heuristics for the maximum diversity problem
• Variable Neighborhood Search
• Different Formulations for Solving the HeaviestK-Subgraph Problem