کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435548 | 689914 | 2016 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Approximation algorithm for the balanced 2-connected k-partition problem Approximation algorithm for the balanced 2-connected k-partition problem](/preview/png/435548.png)
For two positive integers m,km,k and a connected graph G=(V,E)G=(V,E) with a nonnegative vertex weight function w, the balanced m-connected k -partition problem, denoted as BCmPkBCmPk, is to find a partition of V into k disjoint nonempty vertex subsets (V1,V2,…,Vk)(V1,V2,…,Vk) such that each G[Vi]G[Vi] (the subgraph of G induced by ViVi) is m -connected, and min1≤i≤k{w(Vi)}min1≤i≤k{w(Vi)} is maximized. The optimal value of BCmPkBCmPk on graph G is denoted as βm⁎(G,k), that is, βm⁎(G,k)=maxmin1≤i≤k{w(Vi)}, where the maximum is taken over all m-connected k-partition of G . In this paper, we study the BC2PkBC2Pk problem on interval graphs, and obtain the following results.(1) For k=2k=2, a 4/3-approximation algorithm is given for BC2P2BC2P2 on 4-connected interval graphs.(2) In the case that there exists a vertex v with weight at least W/kW/k, where W is the total weight of the graph, we prove that the BC2PkBC2Pk problem on a 2k-connected interval graph G can be reduced to the BC2Pk−1BC2Pk−1 problem on the (2k−1)(2k−1)-connected interval graph G−vG−v. In the case that every vertex has weight at most W/kW/k, we prove a lower bound β2⁎(G,k)≥W/(2k−1) for 2k-connected interval graph G.(3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC2PkBC2Pk problem on 2k-connected interval graphs.
Journal: Theoretical Computer Science - Volume 609, Part 3, 4 January 2016, Pages 627–638