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
論文 | ランダム
- 38. 非接触型変位計を利用した Dilatometer の試作(第 38 回九州歯科学会総会講演抄録)
- 咬合高径の増大に伴う咬合接触時間・回数・持続時間の変化に関する研究 : 論文審査の結果の要旨
- 牛耳下腺細胞質由来の NADP 依存性イソクエン酸脱水素酵素の精製とその性質 : 論文審査の結果の要旨
- Fffect of the Core on Fitness of Dental Casting : 論文審査の結果の要旨
- 下顎窩の X 線学的形態に関する研究 : フーリェ級数による女性下顎窩の形態の解析 : 論文審査の結果の要旨