WEKO3
-
RootNode
アイテム
Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs
http://hdl.handle.net/10252/3049
http://hdl.handle.net/10252/30495eca4826-2590-461b-87e7-c3cb08344844
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
Ishii_Algorithmica.pdf (366.7 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2009-08-10 | |||||
| タイトル | ||||||
| タイトル | Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Undirected graph | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Connectivity augmentation problem | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Edge-connectivity | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Node-to-area connectivity | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Polynomial time deterministic algorithm | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Edge-splitting | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | journal article | |||||
| 著者 |
Ishii, Toshimasa
× Ishii, Toshimasa× Akiyama, Yoko× Nagamochi, Hiroshi |
|||||
| bibliographic_information |
en : Algorithmica 発行日 2008-03-15 |
|||||
| 出版者 | ||||||
| 出版者 | Springer | |||||
| 言語 | en | |||||
| ISSN / EISSN | ||||||
| 収録物識別子タイプ | EISSN | |||||
| 収録物識別子 | 1432-0541 | |||||
| item_1_relation_8 | ||||||
| 関連タイプ | isVersionOf | |||||
| 識別子タイプ | DOI | |||||
| 関連識別子 | info:doi/10.1007/s00453-008-9178-y | |||||
| 出版タイプ | ||||||
| 出版タイプ | AM | |||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||
| 日本十進分類法 | ||||||
| 言語 | ja | |||||
| 主題Scheme | NDC | |||||
| 主題 | 415 | |||||
| NIIサブジェクト | ||||||
| 言語 | ja | |||||
| 主題Scheme | Other | |||||
| 主題 | 数学 | |||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 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}|$ | |||||
| 言語 | en | |||||
Share
Cite as
Ishii, Toshimasa, Akiyama, Yoko, Nagamochi, Hiroshi, 2008, Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs: Springer.
Loading...
