论文标题
$（p，q）$ - 弹性冲突模型的扩展
Extensions of the $(p,q)$-Flexible-Graph-Connectivity model
论文作者
论文摘要
我们在与$（P，Q）$ -FGC模型有关的某些模型中提出了网络设计问题的近似算法。 Adjisshvili，Hommelsheim和Mühlenthaler引入了FGC表示的灵活图连接模型。博伊德（Boyd），切里扬（Cheriyan），哈达丹（Hadadan）和易卜拉欣（Ibrahimpur）引入了FGC的概括。令$ p \ geq 1 $和$ q \ geq 0 $为整数。在$（p，q）$ - 灵活的图形连接问题的情况下，表示$（p，q）$ - fgc，我们有一个无方向的连接图$ g =（v，e）$，将$ e $的分区分为一组安全边缘，并在一组不安全的边缘和一组不安全的边缘，以及一组不使用的边缘，以及$ c \ ceq in \ mathbb $ geq in \ geq $ geq 0}如果对于任何一组不安全的边缘，$ f'u $，带有$ | f'| \ leq q $，子graph $（v，v，f \ setminus f'），子集$ f \ subseteq e $对于$（p，q）$ - fgc问题是可行的（p，q）$ -FGC问题。算法目标是找到一个可行的边缘$ f $，该$ f $最小化$ c（f）= \ sum_ {e \ in F} c_e $。
We present approximation algorithms for network design problems in some models related to the $(p,q)$-FGC model. Adjiashvili, Hommelsheim and Mühlenthaler introduced the model of Flexible Graph Connectivity that we denote by FGC. Boyd, Cheriyan, Haddadan and Ibrahimpur introduced a generalization of FGC. Let $p\geq 1$ and $q\geq 0$ be integers. In an instance of the $(p,q)$-Flexible Graph Connectivity problem, denoted $(p,q)$-FGC, we have an undirected connected graph $G = (V,E)$, a partition of $E$ into a set of safe edges and a set of unsafe edges, and nonnegative costs $c\in\mathbb{R}_{\geq0}^E$ on the edges. A subset $F \subseteq E$ of edges is feasible for the $(p,q)$-FGC problem if for any set of unsafe edges, $F'$, with $|F'|\leq q$, the subgraph $(V, F \setminus F')$ is $p$-edge connected. The algorithmic goal is to find a feasible edge-set $F$ that minimizes $c(F) = \sum_{e \in F} c_e$.
