WEKO3
アイテム
λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1
https://ipsj.ixsq.nii.ac.jp/records/31949
https://ipsj.ixsq.nii.ac.jp/records/31949f7ab6c72-0e02-4a6a-b72b-1db6b894c90f
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2002 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2002-11-08 | |||||||
タイトル | ||||||||
タイトル | λ-辺連結グラフにおける指定点集合の(λ+1)-辺連結化のための2-近似アルゴリズムFSA+1 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A 2 - Approximation Algorithm FSA+1 to (&lambda+1) -Edge- Connect a Specified Set of Vertices in a &lambda -Edge- Connected Graph | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
広島大学大学院工学研究科 | ||||||||
著者所属 | ||||||||
広島国際大学社会環境科学部 | ||||||||
著者所属 | ||||||||
広島大学大学院工学研究科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Faculty of Infrastructural Technologies, Hiroshima International University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Engineering, Hiroshima University | ||||||||
著者名 |
田岡, 智志
× 田岡, 智志
|
|||||||
著者名(英) |
Satoshi, Taoka
× Satoshi, Taoka
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 無向グラフG=(V E),Gの部分グラフ G' = (V E') 指定点集合Γ ⊆ V,コスト関数 c: E → R^+が与えられたとき,Γのk-辺連結化問題 (kECA-SV)を考える.本稿では,λ(V;G') = λ(Γ;G')なる場合の(λ+1)ECA-SVに対し,O(Δ +|V||E|)時間の2-近似アルゴリズムFSA+1を提案する.ここで,λ =λ(Γ;G')とし,ΔはG'の構造グラフF(G')を構成する計算時間複雑度とする. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Given an undirected graph G=(V,E), a subgraph G'=(V,E') of G, a specified set \Gamma \subseteq V, and a cost function c: E \to R^{+}, we consider the k-edge-connectivity augmentation problem for \Gamma (kECA-SV).The paper proposes an O(\Delta +|V||E|) time2-approximation algorithm FSA+1 for (\lambda+1)ECA-SV for the case when \lambda(V;G') = \lambda(\Gamma;G'), where \lambda=\lambda(\Gamma;G') and \Delta is the time complexity of constructing a structural graph F(G') of G'. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2002, 号 103(2002-AL-087), p. 25-32, 発行日 2002-11-08 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |