- 著者
-
加地 太一
大内 東
加地 郁夫
- 雑誌
- 全国大会講演論文集
- 巻号頁・発行日
- vol.40, pp.61-62, 1990-03-14
本論文はノードが番号順に列をなし、あるサイズ以下の部分集合に、カットされるエッジのコストの総和を最小分割する問題である。応用例としてはページングにおける仮想アドレスへのプログラムの最適配置などがある。この問題に対してKernighan[1]はダイナミックプログラミング(DP)を示している。本論文ではこれに対して、Branch-and-Bound法(B&B)法によるアルゴリズムとKernighanによるDPアルゴリズムの改良型(改良型DP)を提案する。