Optimization Online


Hybrid Constructive Heuristics for the Critical Node Problem

Bernadetta Addis(bernardetta.addis***at***loria.fr)
Roberto Aringhieri(roberto.aringhieri***at***unito.it)
Andrea Grosso(grosso***at***di.unito.it)
Pierre Hosteins(hosteins***at***di.unito.it)

Abstract: We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order to obtain simple “hybrid” heuristic algorithm. The obtained algorithms are shown to be effective, delivering improved performances (solution quality and speed) with respect to known greedy algorithms and other more sophisticated state of the art methods.

Keywords: Graph Fragmentation, Critical Node Problem, greedy heuristics

Category 1: Network Optimization

Citation: Dipartimento di Informatica, Università di Torino January 2015

Download: [PDF]

Entry Submitted: 01/29/2015
Entry Accepted: 02/01/2015
Entry Last Modified: 01/29/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society