最小コストフロー問題の高速解法とそのVLSIコンパクション問題への適用

• Item type: SIG Technical Reports(1)
• 公開日: 1995-09-20
• タイトル: 最小コストフロー問題の高速解法とそのVLSIコンパクション問題への適用
• タイトル / 言語: en
• タイトル: A Fast Minimum Cost Flow Algorithm and Its Application to VLSI Layout Compaction
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪大学工学部情報システム工学科
• 著者所属: Department of Electronic King Mongkut's Institute of Technology
• 著者所属: 大阪大学工学部情報システム工学科
• 著者所属: 岡山県立大学情報工学部情報通信学科
• 著者所属(英): en
• 著者所属(英): Department of Information Systems Engineering, Faculty of Engineering, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Electronic, King Mongkut's Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information Systems Engineering, Faculty of Engineering, Osaka University
• 著者所属(英): en
• 著者所属(英): Department of Communication Engineering Faculty of Computer Science and System Engineering, Okayama Prefectural University
• 著者名: 重弘, 裕二; Itthichai, ARUNGSRISANGCHAI; 白川, 功; 高橋, 浩光
• 著者名(英): Yuji, Shigehiro; Itthichai, Arungsrisangchai; Isao, Shirakawa; Hiromitsu, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: VLSIのコンパクション処理に線形計画法を用いることができるが，その時に扱われる線形計画問題は最小コストフロー問題と双対であるので，最小コストフローアルゴリズムを用いた手法が構築できるはずである．そこで，本文ではコンパクション処理に適した最小コストフローアルゴリズムについて，特にこれまで主単体法ほどには研究が行われていなかった主双対法に着目し，それから演繹される高速化手法について考案する．各種最小コストフローアルゴリズムをコンパクション処理に適用した結果，コンパクション処理では，本手法は主単体法以上に速いことがわかった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the layout design of custom VLSI, a number of effective compaction algorithms have been constructed on the basis of linear programming. Since the problem is dual to the minimum cost flow problem, flow algorithms can be applicable to the layout compaction. In this paper, an existing flow algorithm is investigated for the layout compaction, and a fast flow algorithm based on the primal-dual method is proposed. Experimental results show that, for the compaction problem, the dual-simplex method is the fastest of the existing algorithms, and the proposed method is more effective than them.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 情報処理学会研究報告数理モデル化と問題解決（MPS）; 巻 1995, 号 93(1995-MPS-003), p. 37-42, 発行日 1995-09-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会