Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419924 | Discrete Applied Mathematics | 2013 | 12 Pages |
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
Bernardetta Addis, Marco Di Summa, Andrea Grosso,