In this paper, we consider the constrained Steiner strong connectivity augmentation (CStSCA) problem. Concretely, given a weighted digraph \(D=(V,A;w)\) , where \(w:A \rightarrow R^{+}\) is a weight function, K ( \(\subseteq V\) ) is a vertex-set consisting of k fixed vertices (called as terminals) and \(T_{k}=(V_{k},A_{k})\) is a strongly connected Steiner subgraph (of D), i.e., \(T_{k}\) contains at least one directed path from each terminal s to other each terminal t, where s, \(t\in K\) , we are asked to find an arc-set \(A'\subseteq A \backslash A_{k}\) to satisfy the constraints that, given each arc \(e \in A_{k}\) , the subgraph \(D[A' \cup A_{k} \backslash \{e\}]\) is still a strongly connected Steiner subgraph (of D), the objective is to minimize the summation of weights of all arcs in \(A'\) , where the summation is taken among all arc-sets to satisfy the constraints as mentioned-above. In particular, given a vertex-set \(K=\{x,y\}\) , we refer the CStSCA problem as to the constrained directed circuit augmentation (CDCA) problem, and given a vertex-set \(K=V\) , we refer the CStSCA problem as to the constrained strong connectivity augmentation (CSCA) problem. We obtain the following three main results. (1) We design an 2-approximation algorithm to solve the CDCA problem in time O(mn); (2) Using the preceding algorithm in (1) as a subroutine for many times, we present an 2k-approximation algorithm to solve the CStSCA problem in time O(kmn); (3) We provide an 2-approximation algorithm to solve the CSCA problem in time \(O(n(m+n\log n)\log n)\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Constrained Steiner Strong Connectivity Augmentation Problem

  • Junran Lichen,
  • Shuwen Ge,
  • Runtao Xie,
  • Ping Yang

摘要

In this paper, we consider the constrained Steiner strong connectivity augmentation (CStSCA) problem. Concretely, given a weighted digraph \(D=(V,A;w)\) , where \(w:A \rightarrow R^{+}\) is a weight function, K ( \(\subseteq V\) ) is a vertex-set consisting of k fixed vertices (called as terminals) and \(T_{k}=(V_{k},A_{k})\) is a strongly connected Steiner subgraph (of D), i.e., \(T_{k}\) contains at least one directed path from each terminal s to other each terminal t, where s, \(t\in K\) , we are asked to find an arc-set \(A'\subseteq A \backslash A_{k}\) to satisfy the constraints that, given each arc \(e \in A_{k}\) , the subgraph \(D[A' \cup A_{k} \backslash \{e\}]\) is still a strongly connected Steiner subgraph (of D), the objective is to minimize the summation of weights of all arcs in \(A'\) , where the summation is taken among all arc-sets to satisfy the constraints as mentioned-above. In particular, given a vertex-set \(K=\{x,y\}\) , we refer the CStSCA problem as to the constrained directed circuit augmentation (CDCA) problem, and given a vertex-set \(K=V\) , we refer the CStSCA problem as to the constrained strong connectivity augmentation (CSCA) problem. We obtain the following three main results. (1) We design an 2-approximation algorithm to solve the CDCA problem in time O(mn); (2) Using the preceding algorithm in (1) as a subroutine for many times, we present an 2k-approximation algorithm to solve the CStSCA problem in time O(kmn); (3) We provide an 2-approximation algorithm to solve the CSCA problem in time \(O(n(m+n\log n)\log n)\) .