標題: 有水平限制的通道繞線(CHANNEL ROUTING WITH HORIZONTAL CONST RAINTS)
作者: 劉以專
LIU, YI-ZHUAN
郭譽申
GUO, YU-SHEN
資訊科學與工程研究所
關鍵字: 水平限制;通道繞線;垂直限制;網路;軌道;變數;誤差;HORIZONTAL-CONSTRAINTS;CHANNEL-ROUTING
公開日期: 1984
摘要: 本論文是探討有水平限制的通道繞線問題。此問題染有垂直限制,在通道內每一網路 至多允許佔有一條水平線段,並且有假設有幾條水平軌道的兩邊事先已被佔用。如因 軌道數目是收數,則本文證明此問題是NP_COMPLETE。如困軌道數目是固 定的,則提出一個能在多項式時間內解決此問題的運算法則。同時也提出一個有誤差 上限的啟發式運算法則來解決問題。最後,再證明一個相關的問題CHSSFT是N P-COMPLETE。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT732241032
http://hdl.handle.net/11536/51982
Appears in Collections:Thesis