@techreport{oai:ipsj.ixsq.nii.ac.jp:00240472,
 author = {李, 宣岐 and 今川, 隆司 and 越智, 裕之},
 issue = {5},
 month = {Oct},
 note = {本稿では，従来の 2 端子のナンバーリンクの拡張問題である多端子ナンバーリンクを対象とし，その全ての解を列挙するアルゴリズムを改良する．ナンバーリンクは理論的には NP 完全問題であり，実際には VLSI および PCB の平面配線を模倣しているため，これを解くための様々なアルゴリズムが開発されている．トップダウン ZDD 構築法を用いた既存手法により，ナンバーリンクの全ての解を効率的に列挙でき，これによって得られるナンバーリンクの解の個数は配線の代替経路の多さを表していると考えられ，FPGA 等の配線アーキテクチャの配線自由度などの評価指標としての利用が期待される．しかしこの ZDD ベースのアルゴリズムは，各ネットがちょうど 2 つの端子を持つというナンバーリンクの前提に特化されており，実際の配線対象となる回路とは乖離している．我々はマルチファンアウトのネットを配線できる，多端子ナンバーリンク用に拡張した ZDD ベースのアルゴリズムを提案したが，これを 2 端子のナンバーリンクに適用した時のオーバヘッドが大きいことが課題であった．本稿はこれを改善するため，総分岐数超過の検出を導入する．},
 title = {トップダウンZDD構築法を用いた多端子ナンバーリンク問題の全解探索アルゴリズムの改良},
 year = {2024}
}