ビンの容量を制限したキューブパッキング問題のNP完全性について

書誌事項

タイトル別名
  • Cube-Packing Problem with Fixed Bin-Capacity(≧3)is NP-complete

この論文をさがす

説明

Look Up Table(LUT)ベースのFPGAのテクノロジーマッピングにおいて,2段部分回路のLUTへの割り当てはキャーブパッキング問題として定式化できる.共通信号線の効果を考慮しない場合にはビンパッキング問題として定式化でき,LUTの入力線数を現実的な値に限ると高速に最適解を求めることができる.本論文ではLUTの入力線数を固定した場合のキューブパッキング問題の計算複雑度を考察し,NP完全であることを証明する.
In technology mapping of Look Up Table(LUT)based FPGA,the problem of mapping a two-level subcircuit into LUTs is formulated as the Cube-Packing problem.Without taking account of the advantage of a signal to multiple gates,it is formulated as the Bin-Packing problem.If the number of inputs of LUTs is limited to a practical value,the Bin-Packing problem can be solved optimally very fast.In this paper,we consider the computational complexity of the Cube-Packing in the case that the number of inputs of LUTs is fixed,and prove the problem to be NP-complete.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1572543027237806592
  • NII論文ID
    110003194271
  • NII書誌ID
    AN10012998
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ