集合対間配線における目標端子対選択法に関する一検討

摘要

集合対間配線問題に対し，配線長と配線長差の小さい配線パターンを効率よく生成することを目指し，（1）目標端子対を設定し，（2）それら目標端子対をできる限り接続する配線パターンを初期解とし生成，修正する手法を検討している．本稿では，（1）において，離れた端子の対をできる限り含まない目標端子対の集合を選択する方法を提案する．目標端子対集合の選択を，二部グラフにおける辺重みの最大値が最小な完全マッチングを求める問題として定式化し，提案アルゴリズムは，辺重みの最大値が最小な完全マッチングを出力する．考察では提案するアルゴリズムの有効性を検討する．