@techreport{oai:ipsj.ixsq.nii.ac.jp:00031909,
 author = {渡辺, 一哉 and 高藤, 大介 and 田岡, 智志 and 渡邉, 敏正 and Kazuya, Watanabe and Daisuke, Takafuji and Satoshi, Taoka and Toshimasa, Watanabe},
 issue = {92(2003-AL-091)},
 month = {Sep},
 note = {需要点集合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|}を求める. これらの需要点集合に属する需要点の需要量総和が最大となるような需要点集合族を求める問題を”グラフの最大供給分割問題”と呼ぶ. 本稿では  グラフの最大供給分割問題に対する既存の発見的解法と最適解法に着目し  提案する改良手法と共に計算機上で実装して  これらの性能を計算機実験により比較評価する., 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.},
 title = {グラフに対する最大供給分割問題解法の性能評価},
 year = {2003}
}