Node-weighted Network Design in Planar and Minor-closed Families of Graphs
Node-weighted Network Design in Planar and Minor-closed Families of Graphs
复制标题
DOI：
10.1145/3447959
复制
发表时间：
2012-07
期刊：
影响因子：
--
通讯作者：
C. Chekuri;Alina Ene;A. Vakilian
中科院分区：
文献类型：
--
作者：
C. Chekuri;Alina Ene;A. Vakilian
我们考虑了平面图和次要闭合图家族中的节点加权可生存的网络设计（SNDP）。输入由节点加权的无向图G =（v，e）和整数连接要求R（UV）对于每对node uv uv。目标是找到G的最小加权子图H，以使H在每个节点对UV的U和V之间包含R（UV）的分离路径。该问题的三个版本是边缘连接性SNDP（EC-SNDP），元素 - 连接性SNDP（ELEM-SNDP）和顶点连接性SNDP（VC-SNDP），具体取决于是否需要路径是边缘，元素，元素，元素，，，，，，，，，，，，，，元素或顶点偏离。我们的主要结果是当输入图属于适当的次要少量闭合图的图形时，EC-SNDP和ELEM-SNDP的O（K） - Approximation算法是平面或更一般的。在这里，k =最大UVR（UV）是最大连接性要求。这改善了O（klog n） - 对淋巴结加权EC-SNDP和ELEM-SNDP的O（Klog n） - apptroximation [31]。当连接性要求在{0、1、2}中时，我们还获得了节点加权VC-SNDP的O（1）近似值；为了更高的连接性，我们的Elem-SNDP的结果可以以黑盒方式使用，以获得比对数因子的改进，而不是当前已知的一般图形结果。我们的结果灵感来自于Demaine，Hajiaghayi和Klein [13]的启发，并获得了在平面图中获得节点加权的Steiner Tree和Steiner Forest问题的恒定因子近似值，并通过适当的少量封闭的图形家庭通过原始二算法。
We consider node-weighted survivable network design (SNDP) in planar graphs and minor-closed families of graphs. The input consists of a node-weighted undirected graph G = (V, E) and integer connectivity requirements r(uv) for each unordered pair of nodes uv. The goal is to find a minimum weighted subgraph H of G such that H contains r(uv) disjoint paths between u and v for each node pair uv. Three versions of the problem are edge-connectivity SNDP (EC-SNDP), element-connectivity SNDP (Elem-SNDP), and vertex-connectivity SNDP (VC-SNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O(k)-approximation algorithm for EC-SNDP and Elem-SNDP when the input graph is planar or more generally if it belongs to a proper minor-closed family of graphs; here, k = max uvr(uv) is the maximum connectivity requirement. This improves upon the O(klog n)-approximation known for node-weighted EC-SNDP and Elem-SNDP in general graphs [31]. We also obtain an O(1) approximation for node-weighted VC-SNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our result for Elem-SNDP can be used in a black-box fashion to obtain a logarithmic factor improvement over currently known general graph results. Our results are inspired by, and generalize, the work of Demaine, Hajiaghayi, and Klein [13], who obtained constant factor approximations for node-weighted Steiner tree and Steiner forest problems in planar graphs and proper minor-closed families of graphs via a primal-dual algorithm.