グラフに対する最大供給分割問題解法の性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2003-09-19
• タイトル: グラフに対する最大供給分割問題解法の性能評価
• タイトル / 言語: en
• タイトル: Experimental Evaluation of Algorithms for Maximum - Supply Partitioning of a Demand - Supply Graph
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者名: 渡辺, 一哉; 高藤, 大介; 田岡, 智志; 渡邉, 敏正
• 著者名(英): Kazuya, Watanabe; Daisuke, Takafuji; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 需要点集合Vdと供給点集合Vsの和集合である点集合 および無向辺集合Eを持つグラフG＝(Vd ∪ Vs E) さらに各需要点vの需要量d(v)＞0 各供給点uの供給量s(u)＞0が与えられたとする. 各供給点uk(1≦k≦|Vs|)に対して Σv∈Vdkb d(v)≦s(uk)かつVdk ∪{uk}のGでの誘導部分グラフが連結であるような 互いに素な需要点集合Vdkの族{Vdk|1≦k≦|Vs|}を求める. これらの需要点集合に属する需要点の需要量総和が最大となるような需要点集合族を求める問題を”グラフの最大供給分割問題”と呼ぶ. 本稿では グラフの最大供給分割問題に対する既存の発見的解法と最適解法に着目し 提案する改良手法と共に計算機上で実装して これらの性能を計算機実験により比較評価する.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let G＝(Vd ∪ Vs,E) be an undirected graph with two disjoint vertex sets: Vd of demand vertices and Vs of supply ones. Suppose that a positive value d(v) or s(v) is assigned to each demand or supply vertex v, respectively. Let Vd1,...,Vd|Vs| be a patition of Vd such that, for each uk ∈ Vs (1 ≦ k ≦ |Vs|), (i) the subgraph G[Vdk ∪{uk}] induced by Vdk ∪{uk} of G is connected, and (ii) Σv∈Vdk d(v) ≦ s(uk). The maximum-supply partition problem for a given demand-supply graph is to find such a partition with Σ1≦k≦|Vs| d(Vdk) being maximum, where d(Vdk)＝Σv∈Vdk d(v). This paper proposes improved versions of several known algorithms: one of them gives an optimum solution and all others produce heuristic ones, This performance is evaluated based on experimental results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 92(2003-AL-091), p. 59-66, 発行日 2003-09-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会