Approximating multiroot 3-outconnected subgraphs

作     者：Nutov, Z 

作者机构：Open Univ Israel Ramat Aviv Israel 

出 版 物：《NETWORKS》 (网络)

年 卷 期：2000年第36卷第3期

页      面：172-179页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：approximation algorithm rooted 3-outconnected subgraph 

摘      要：Consider the following problem: Given an undirected graph with nonnegative edge costs and requirements k(u) for every node u, find a minimum-cost subgraph that contains max{k(u), k(v)} internally disjoint paths between every pair of nodes u, v. For k = max k(u) greater than or equal to 2, this problem is NP-hard. The best-known algorithm for it has an approximation ratio of 2(k - 1). For a general instance of the problem, for no value of k greater than or equal to 2, a better approximation algorithm was known. We consider the case of small requirements k(u) epsilon {1, 2, 3};these may arise in applications, as, in practical networks, the connectivity requirements are usually rather small. For this case, we give an algorithm with an approximation ratio of 10/3. This improves the best previously known approximation ratio of 4. Our algorithm also implies an improvement for arbitrary k. In the case in which we have an initial graph which is 2-connected, our algorithm achieves an approximation ratio of 2. (C) 2000 John Wiley & Sons, Inc.