Critical edges/nodes for the minimum spanning tree problem: complexity and approximation |
| |
Authors: | Cristina Bazgan Sonia Toubaline Daniel Vanderpooten |
| |
Institution: | 1. LAMSADE, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775, Paris Cedex 16, France 2. Institut Universitaire de France, Paris, France
|
| |
Abstract: | 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?? , for any ?>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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|