Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

被引：23

作者：

Bazgan, Cristina ^{[1
]}

Toubaline, Sonia ^{[1
]}

Vanderpooten, Daniel ^{[1
]}

机构：

[1] Univ Paris 09, LAMSADE, F-75775 Paris, France

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2013年 / 26卷 / 01期

关键词：

Most vital edges/nodes; Min edge/node blocker; Minimum spanning tree; Complexity; Approximation; VITAL EDGES; RESPECT; INTERDICTION; NETWORK;

D O I：

10.1007/s10878-011-9449-4

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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.

引用

页码：178 / 189

页数：12

共 19 条

[1]

Arora Sanjeev., 1996, APPROXIMATION ALGORI, P399

[2]

Bar-Noy A., 1995, CSTR3539 U MAR

[3]

Bazgan C, 2011, LECT NOTES COMPUT SC, V6831, P126, DOI 10.1007/978-3-642-22616-8_11

[4]

Bazgan C, 2010, LECT NOTES COMPUT SC, V6508, P237, DOI 10.1007/978-3-642-17458-2_20