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 isNP-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.
Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth
GROSSO, Andrea Cesare
2013-01-01
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 isNP-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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
cnp-final_4aperto.pdf
Accesso aperto
Tipo di file:
POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione
340.16 kB
Formato
Adobe PDF
|
340.16 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
