有水平限制的通道繞線(CHANNEL ROUTING WITH HORIZONTAL CONST RAINTS)

Abstract

本論文是探討有水平限制的通道繞線問題。此問題染有垂直限制，在通道內每一網路 至多允許佔有一條水平線段，並且有假設有幾條水平軌道的兩邊事先已被佔用。如因 軌道數目是收數，則本文證明此問題是ＮＰ＿ＣＯＭＰＬＥＴＥ。如困軌道數目是固 定的，則提出一個能在多項式時間內解決此問題的運算法則。同時也提出一個有誤差 上限的啟發式運算法則來解決問題。最後，再證明一個相關的問題ＣＨＳＳＦＴ是Ｎ Ｐ－ＣＯＭＰＬＥＴＥ。