標題: 線路佈局中之分割問題與最小相交問題
作者: 汪厚燊
WANG, HOU-SHEN
徐力行
XU, LI-XING
應用數學系所
關鍵字: 邏輯電路
公開日期: 1986
摘要: 在超大型積體電路的線路佈局裡,分割重要的工具。利用圖的模型,我們將分割問題 數學化;以點代表邏輯電路中的組成單元,以線代表其電路連接的情形。並介一種常 用的交換式分割方法。我們也考慮以圖的接鄰矩陣來討論的分割方法,因而得到最小 外連接數的下界。 最小相交數提供了分割線路成為兩個部份的最低代價。我們的主要興趣便放在最大流 量最小相交定理和演算法。由上述觀點,我們研究了多重端點的最小相交問題和使用 一個更適合電路的相交綱路模型。最後,結合多重端點和相交網路的最小相交的演算 法,我們可以計算所有單元之間的最小相連數。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT752507015
http://hdl.handle.net/11536/53145
顯示於類別:畢業論文