標題: | 有水平限制的通道繞線(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 |
顯示於類別: | 畢業論文 |