グラフの最適系列分割アルゴリムの改善

• 加地, 太一

• 大内, 東

• 加地, 郁夫

書誌事項

タイトル別名

• Improvement for Optimal Suquential Partitions of Graphs

抄録

本論文はノードが番号順に列をなし、あるサイズ以下の部分集合に、カットされるエッジのコストの総和を最小分割する問題である。応用例としてはページングにおける仮想アドレスへのプログラムの最適配置などがある。この問題に対してKernighan[1]はダイナミックプログラミング(DP)を示している。本論文ではこれに対して、Branch-and-Bound法(B&B)法によるアルゴリズムとKernighanによるDPアルゴリズムの改良型(改良型DP)を提案する。

収録刊行物

• 全国大会講演論文集

  全国大会講演論文集 第40回 (基礎理論及び基礎技術), 61-62, 1990-03-14

詳細情報

• CRID: 1050574047077650816
• NII論文ID: 110002883451
• NII書誌ID: AN00349328
• Web Site: http://id.nii.ac.jp/1001/00118350/
• 本文言語コード: ja
• 資料種別: conference paper
• データソース種別:
  • IRDB
  • CiNii Articles