| 講演名 | 2005-01-28 需要-供給グラフに対する最大供給分割問題解法の性能評価 渡邉 一哉, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 点集合として需要点の集合V_dと供給点の集合V_sを持ち, 無向辺集合V_sを持つグラフG=(V_d∪V_s, E)において, 各需要点には正数の需要量が, 各供給点には正数の供給量が与えられているとする.点集合を次のようないくつかの部分集合に分割する : 各部分集合に属する点からなるGの誘導部分グラフは連結で, 各部分集合に属する供給点は高々1つであり, 供給点を含む集合についてその集合に属する全需要点の需要量の総和が, その供給点の供給量以下である.このとき, 供給点を含む部分集合に属する全ての需要点の需要量の総和が最大となるような分割された部分集合を求める問題を"グラフの最大供給分割問題"と呼ぶ.本研究では, グラフの最大供給分割問題の発見的解法および最適解法に関して, 既存解法の修正解法, および改良解法を示し, これらを計算機上で実装して性能の比較評価を行う. |
| 抄録(英) | Let G=(V_d∪V_s, E) be an undirected graph with a vertex set V_d∪V_s and an (undirected) edge set E, where the vertex set is partitioned into two subsets, a demand vertex set V_d and a supply vertex set V_s. We assume that V_d≐̸0 and V_s≐̸0 in this paper. Each demand or supply vertex ν has a positive real number d(ν) or s(ν), called the demand or supply of ν, respectively. For any subset V′⊆V_d∪V_s, the demand of V′ is defined by d(V′)=Σ_<ν⋴V′∩V_d>d(ν) if V′∩V_s≐̸0 or d(V′)=0 if V′∩V_s=0. Any partition π={V_1, …, V_p} (p≧1) of V_d∪V_s such that |V_k∩V_s|≦1, the induced subgraph G[V_k] of G is connected, and if |V_k∩V_s|≦{u_k} then d(V_k)≦s(u_k), for any k-1≦k≦p is called a feasible partition of G. The demand d(π) of π is defined by d(π)=Σ_<1≦k≦p>d(V_k). The "Maximum-Supply Partitioning Problem (MSPP)" is to find a feasible partition π of G such that d(π) is maximum among all feasible partitions of G. We implemented not only existing algorithms for obtainity heuristic or optimum solutions to MSPP but also those that are corrected or improved from existing ones. In this paper we show comparison of their capability based on computational experiments. |
| キーワード(和) | グラフ / 分割問題 / 発見的解法 / 最適解法 / 需要 / 供給 |
| キーワード(英) | graphs / partitioning problems / heuristic algorithms / optimal algorithms / demand / supply |
| 資料番号 | COMP2004-67 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/1/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 需要-供給グラフに対する最大供給分割問題解法の性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graphs |
| キーワード(2)（和/英） | 分割問題 / partitioning problems |
| キーワード(3)（和/英） | 発見的解法 / heuristic algorithms |
| キーワード(4)（和/英） | 最適解法 / optimal algorithms |
| キーワード(5)（和/英） | 需要 / demand |
| キーワード(6)（和/英） | 供給 / supply |
| 第 1 著者 氏名（和/英） | 渡邉 一哉 / Kazuya WATANABE |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2005-01-28 |
| 資料番号 | COMP2004-67 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 642 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |