On Rooted k-Connectivity Problems in Quasi-Bipartite Digraphs
On Rooted k-Connectivity Problems in Quasi-Bipartite Digraphs
复制标题
准二分图中的根源 k-连通性问题
DOI：
10.1007/978-3-030-79416-3_20
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zeev Nutov
中科院分区：
文献类型：
--
作者：
Zeev Nutov
我们考虑有向最小代价有根子集k-边连接问题：给定一个有向图$$G=(V，E)$$G=(V，E)，一个终端集合$$T\子集V$$T⊆V，一个根结点r，一个整数k，找到G的一个最小代价子图，它包含T$$t∈T中所有$$t\的k条边不相交的RT-路.由于Frank(离散应用数学157(6)：1242-1254,2009)，当所有正代价边都在T中有头的情况下允许多项式时间算法，而当所有正代价边都关联于r时，等价于k-多覆盖问题。Chan等人。(Approx/RANDOM，2020)给出了一个基于Lp的$$O(\ln k\ln|T|)$$O(ln k ln|T|)-近似算法，当G中的每条边至少有一个末端在$$T\cp\r\$$T∪{r}中时。对于更一般的用最小代价边集覆盖任意T相交超模集合函数的问题，以及当每条正代价边在$T∪{r}中至少有一端时，我们给出了一个具有相同逼近比的简单组合算法.
We consider the directed Min-Cost Rooted Subset k -Edge-Connection problem: given a digraph $$G=(V,E)$$ G = ( V , E ) with edge costs, a set $$T \subseteq V$$ T ⊆ V of terminals, a root node r , and an integer k , find a min-cost subgraph of G that contains k edge disjoint rt -paths for all $$t \in T$$ t ∈ T . The case when every edge of positive cost has head in T admits a polynomial time algorithm due to Frank (Discret Appl Math 157(6):1242–1254, 2009 ), and the case when all positive cost edges are incident to r is equivalent to the k -Multicover problem. Chan et al. (APPROX/RANDOM, 2020 ) gave an LP-based $$O(\ln k \ln |T|)$$ O ( ln k ln | T | ) -approximation algorithm for quasi-bipartite instances, when every edge in G has at least one end in $$T \cup \{r\}$$ T ∪ { r } . We give a simple combinatorial algorithm with the same approximation ratio for a more general problem of covering an arbitrary T -intersecting supermodular set function by a min-cost edge set, and for the case when only every positive cost edge has at least one end in $$T \cup \{r\}$$ T ∪ { r } .