An instance of the k -generalized connectivity problem consists of an undirected graph G=(V,E), whose edges are associated with non-negative costs, and a collection D={(S1,T1),¼,(Sd,Td)}{mathcal{D}}={(S_{1},T_{1}),ldots,(S_{d},T_{d})} of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ℋ⊆G connects a demand (S i ,T i ) when it contains a path with one endpoint in S i and the other in T i . Given an integer parameter k, the goal is to identify a minimum cost subgraph that connects at least k demands in D{mathcal{D}} .
展开▼
机译：第k个广义连通性问题的一个实例包括一个无向图G =（V，E），其边与非负成本相关，以及一个集合D = {（S 1 ，T 1 ），¼，（S d ，T d ）} {数学{D}} = {（S_ {1}，T_ { 1}），ldots，（S_ {d}，T_ {d}）}具有不同的需求，每个需求包括一对不相交的顶点集。我们说子图ℋ⊆G在包含一个在S i 中具有一个端点的路径时连接了需求（S i ，T i ）。另一个在T i 中。给定整数参数k，目标是确定最小成本子图，该子图连接D {mathcal {D}}中的至少k个需求。
展开▼
