Abstract
通道拉線問題是超大型積體電路自動化設計工作中重要的一環，一個良好的通道拉線工具可以縮小晶片所需的面積。這個問題已被證明是NP-完全，所以如何設計一個快速的計算方法十分重要。本篇論文提出了一個有效的計算方法去求最佳解。雖然在最差狀況需要exponential time，但是根據理論及實驗均顯示這個計算方法在平均狀況十分有效。我們已將這個方法寫成PASCAL程式放在VAX11/750 中執行。對於其他文獻中舉出最複雜的Deutsch difficult case而言，本計算方法也只要5 分半鐘。這個計算方法應用了優勢法則（dominance rules ），理論上證明它可以大幅縮小尋找最佳解的時間。我們提出了一個有效的資料結構來處理這個法則。我們建立了一些分析模式對這個計算方法做了完整的分析。