-

 

 

 




Optimization Online





 

Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth

Bernardetta Addis(addis***at***di.unito.it)
Marco Di Summa(disumma***at***math.unipd.it)
Andrea Grosso(grosso***at***di.unito.it)

Abstract: We consider the problem of deleting a limited number of nodes from a graph in order to minimize a connectivity measure between the surviving nodes. We prove that the problem is $NP$-complete even on quite particular types of graph, and define a dynamic programming recursion that solves the problem in polynomial time when the graph has bounded treewidth. We also extend this polynomial algorithm to several variants of the problem.

Keywords: Critical node problem, treewidth, complexity, dynamic programming

Category 1: Combinatorial Optimization

Citation:

Download: [PDF]

Entry Submitted: 07/29/2011
Entry Accepted: 07/29/2011
Entry Last Modified: 07/29/2011

Modify/Update this entry


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

 

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