排序方式: 共有4条查询结果,搜索用时 15 毫秒
1
1.
Bazgan Cristina Beaujean Paul Gourdin Éric 《Journal of Combinatorial Optimization》2022,44(3):1880-1899
Journal of Combinatorial Optimization - Modifying the topology of a network to mitigate the spread of an epidemic with epidemiological constant $$\lambda $$ amounts to the NP-hard problem of... 相似文献
2.
Complexity of determining the most vital elements for the p-median and p-center location problems 总被引:1,自引:1,他引:0
Cristina Bazgan Sonia Toubaline Daniel Vanderpooten 《Journal of Combinatorial Optimization》2013,25(2):191-207
We consider the k most vital edges (nodes) and min edge (node) blocker versions of the p-median and p-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) p-median (respectively p-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the p-median (respectively p-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker p-median (respectively p-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the p-median (respectively p-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges p-median and k most vital edges p-center are NP-hard to approximate within a factor $\frac{7}{5}-\epsilon$ and $\frac{4}{3}-\epsilon$ respectively, for any ?>0, while k most vital nodes p-median and k most vital nodes p-center are NP-hard to approximate within a factor $\frac{3}{2}-\epsilon$ , for any ?>0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36. 相似文献
3.
Critical edges/nodes for the minimum spanning tree problem: complexity and approximation 总被引:1,自引:1,他引:0
Cristina Bazgan Sonia Toubaline Daniel Vanderpooten 《Journal of Combinatorial Optimization》2013,26(1):178-189
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. 相似文献
4.
Bazgan Cristina Herzel Arne Ruzika Stefan Thielen Clemens Vanderpooten Daniel 《Journal of Combinatorial Optimization》2022,43(5):1328-1358
Journal of Combinatorial Optimization - In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is... 相似文献
1