すべての目標値に対し辺連結度増加問題をÕ（mn）時間で解くアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1996-10-17
• タイトル: すべての目標値に対し辺連結度増加問題をÕ（mn）時間で解くアルゴリズム
• タイトル / 言語: en
• タイトル: Augmenting Edge - Connectivity over the Entire Range in Õ (nm) Time
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学工学研究科数理工学教室
• 著者所属: 京都大学工学研究科数理工学教室
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Physics Graduate School of Engineering Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Applied Mathematics and Physics Graduate School of Engineering Kyoto University
• 著者名: 永持仁; 茨木, 俊秀
• 著者名(英): Hiroshi, Nagamochi; Toshihide, Ibaraki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: G=(，E，c_)を辺に非負の実数値重みを持つ無向グラフとする。Gの各点対間に重みを付加してグラフの辺連結度を指定された目標値kに増加させる問題を考える。このとき、新たに加える重みの総量は最小にするものとする。このGの辺連結度をkに増加させるために付加すべき重みの最小必要量をΛ_G(）と記し、G^*(）で最適に辺連結度をkにさせた(つの）グラフを表すとする。最近、与えられたグラフGに対する関数Λ_G(），k∈[0，+∞]を決定するO(m+n^2 log )時間のアルゴリズムが提案された。ここで、n=|V|，m=|E|．本報告では、関数Λ_Gを計算するために用いられたデータに基づけば、すべてのk∈[0，+∞]に対する最適解G^*(）をO( log )個の閉路として表現でき、そのような閉路集合をO(m+n^2 log )時間で計算できることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: For a given undirected graph G=(V,E,c_G) with edges weighted by nonnegative reals c_G : E → R^+, let Λ_G(k) stand for the minimum amount of weights to be added to make G k-edge-connected, and G^*(k) be the resulting graph obtained from G. Recently, it is shown that function Λ_G(k) over the entire range k∈[0,+∞] can be computed in O(nm+n^2 log n) time, where n and m are the numbers of vertices and edges, respectively. This paper shows that all G^*(k) in the entire range can be obtained from O(n log n) weighted cycles, and such cycles can be computed in O(nm+n^2 log n) time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 100(1996-AL-054), p. 49-56, 発行日 1996-10-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会