Article ID Journal Published Year Pages File Type
419924 Discrete Applied Mathematics 2013 12 Pages PDF
Abstract

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

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,