首页 | 本学科首页   官方微博 | 高级检索  
     


The Minimum Vulnerability Problem
Authors:Sepehr Assadi  Ehsan Emamjomeh-Zadeh  Ashkan Norouzi-Fard  Sadra Yazdanbod  Hamid Zarrabi-Zadeh
Affiliation:1. Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
Abstract:We revisit the problem of finding (k) paths with a minimum number of shared edges between two vertices of a graph. An edge is called shared if it is used in more than one of the (k) paths. We provide a ({lfloor {k/2}rfloor }) -approximation algorithm for this problem, improving the best previous approximation factor of (k-1) . We also provide the first approximation algorithm for the problem with a sublinear approximation factor of (O(n^{3/4})) , where (n) is the number of vertices in the input graph. For sparse graphs, such as bounded-degree and planar graphs, we show that the approximation factor of our algorithm can be improved to (O(sqrt{n})) . While the problem is NP-hard, and even hard to approximate to within an (O(log n)) factor, we show that the problem is polynomially solvable when (k) is a constant. This settles an open problem posed by Omran et al. regarding the complexity of the problem for small values of (k) . We present most of our results in a more general form where each edge of the graph has a sharing cost and a sharing capacity, and there is a vulnerability parameter (r) that determines the number of times an edge can be used among different paths before it is counted as a shared/vulnerable edge.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号