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

完整後設資料紀錄

DC 欄位	值	語言
dc.contributor.author	劉以專	en_US
dc.contributor.author	LIU, YI-ZHUAN	en_US
dc.contributor.author	郭譽申	en_US
dc.contributor.author	GUO, YU-SHEN	en_US
dc.date.accessioned	2014-12-12T02:02:58Z	-
dc.date.available	2014-12-12T02:02:58Z	-
dc.date.issued	1984	en_US
dc.identifier.uri	http://140.113.39.130/cdrfb3/record/nctu/#NT732241032	en_US
dc.identifier.uri	http://hdl.handle.net/11536/51982	-
dc.description.abstract	本論文是探討有水平限制的通道繞線問題。此問題染有垂直限制，在通道內每一網路至多允許佔有一條水平線段，並且有假設有幾條水平軌道的兩邊事先已被佔用。如因軌道數目是收數，則本文證明此問題是ＮＰ＿ＣＯＭＰＬＥＴＥ。如困軌道數目是固定的，則提出一個能在多項式時間內解決此問題的運算法則。同時也提出一個有誤差上限的啟發式運算法則來解決問題。最後，再證明一個相關的問題ＣＨＳＳＦＴ是ＮＰ－ＣＯＭＰＬＥＴＥ。	zh_TW
dc.language.iso	zh_TW	en_US
dc.subject	水平限制	zh_TW
dc.subject	通道繞線	zh_TW
dc.subject	垂直限制	zh_TW
dc.subject	網路	zh_TW
dc.subject	軌道	zh_TW
dc.subject	變數	zh_TW
dc.subject	誤差	zh_TW
dc.subject	HORIZONTAL-CONSTRAINTS	en_US
dc.subject	CHANNEL-ROUTING	en_US
dc.title	有水平限制的通道繞線(CHANNEL ROUTING WITH HORIZONTAL CONST RAINTS)	en_US
dc.type	Thesis	en_US
dc.contributor.department	資訊科學與工程研究所	zh_TW
顯示於類別：	畢業論文