WEKO3
アイテム
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
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
|
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 |