Journal
JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume 26, Issue 1, Pages 178-189Publisher
SPRINGER
DOI: 10.1007/s10878-011-9449-4
Keywords
Most vital edges/nodes; Min edge/node blocker; Minimum spanning tree; Complexity; Approximation
Ask authors/readers for more resources
In this paper, we study the complexity and the approximation of the k most vital edges (nodes) and min edge (node) blocker versions for the minimum spanning tree problem (MST). We show that the k most vital edges MST problem is NP-hard even for complete graphs with weights 0 or 1 and 3-approximable for graphs with weights 0 or 1. We also prove that the k most vital nodes MST problem is not approximable within a factor n (1-I mu) , for any I mu > 0, unless NP=ZPP, even for complete graphs of order n with weights 0 or 1. Furthermore, we show that the min edge blocker MST problem is NP-hard even for complete graphs with weights 0 or 1 and that the min node blocker MST problem is NP-hard to approximate within a factor 1.36 even for graphs with weights 0 or 1.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available