Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
スポンサーリンク
概要
- 論文の詳細を見る
Given an undirected multigraph G=(V,E), a family $\mathcal{W}$ of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area $W\in \mathcal{W}$ . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k 3+n 2)(p+kn+nlog n)log k+pkn 3log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and $p=|\mathcal{W}|$
- 2008-03-15
論文 | ランダム
- 当科で経験したUAE後に妊娠に至った症例についての検討
- P4-66 Oncostatin MとHGF(hepatic growth factor)の新生児黄疸への関与(Group101 合併症妊娠5,一般演題,第60回日本産科婦人科学会学術講演会)
- P2-119 妊娠中におけるRetinol binding protein 4(RBP4)とインスリン抵抗性との関連性についての検討(Group48 合併症妊娠2,一般講演,第60回日本産科婦人科学会学術講演会)
- P1-149 糖変動パターンによる絨毛細胞障害に関する研究(Group17 胎盤2,一般演題,第60回日本産科婦人科学会学術講演会)
- P1-102 当科で経験したUAE後に妊娠に至った5症例についての検討(Group12 妊娠高血圧症候群1,一般演題,第60回日本産科婦人科学会学術講演会)