Optimization Online


Branch and cut algorithms for detecting critical nodes in undirected graphs

Marco Di Summa (disumma***at***math.unipd.it)
Andrea Grosso (grosso***at***di.unito.it)
Marco Locatelli (locatell***at***ce.unipr.it)

Abstract: In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results.

Keywords: Critical Node Problem, Branch and Cut, Valid Inequalities, Reformulation-Linearization Technique

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 07/25/2011
Entry Accepted: 07/25/2011
Entry Last Modified: 11/28/2011

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