ログイン
言語:

WEKO3

  • トップ
  • ランキング


インデックスリンク

インデックスツリー

  • RootNode

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 学術雑誌論文

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/3049
5eca4826-2590-461b-87e7-c3cb08344844
名前 / ファイル ライセンス アクション
Ishii_Algorithmica.pdf 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

WEKO 5588

en Ishii, Toshimasa

Search repository
Akiyama, Yoko

× Akiyama, Yoko

WEKO 5589

en Akiyama, Yoko

Search repository
Nagamochi, Hiroshi

× Nagamochi, Hiroshi

WEKO 5590

en Nagamochi, Hiroshi

Search repository
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
戻る
0
views
See details
Views

Versions

Ver.1 2023-05-15 16:02:27.054366
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

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...

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR 2.0
  • OAI-PMH JPCOAR 1.0
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3