陳怡靜等人於2004年時,藉由取代金字塔網路上每一個網格 (mesh) 為圓盤網格(torus) 的作法提出一種新的階層結構,稱之為增強型金字塔網路。近年來,已經有一些關於增強型金字塔網路上拓樸特性與通訊方法的研究。這些研究結果指出,增強型金字塔網路相對於金字塔網路而言,是具有吸引力的替代方案。為了能夠評估一個快速平行通訊互聯網路的可靠度與容錯能力、最大平行度與最小傳輸延遲,在此網路上建置點不相交路徑,並且決定其寬直徑是非常重要的議題。在一個互聯網路上兩個不同節點之間,可能會有許多不同的不相交路徑集。在一個連結度為κ的網路上,任意兩個節點之間建立ω小於等於κ之ω-寬度的最佳不相交路徑集,並且計算出其w-寬直徑是非常困難的。因為增強型金字塔網路的連結度為4,依據Menger定理與其變化形式可知,增強型金字塔網路上任意兩節點之間,至少存在4條節點不相交路徑。本研究首先提出數個新穎的演算法,在n-層增強型金字塔網路上,每組相異兩節點間都建立長度盡可能短寬度為2-,3- 及 4-的不相交路徑集,並且計算出其2-,3- 及 4-寬直徑之上限值。其次,在特定兩節點間分別建立2,3 及 4條路徑。分別而言,這些路徑的長度最多是寬度2-,3- 及 4-的最佳不相交路徑集的長度,並且分別等於此n-層增強型金字塔網路2-,3- 及 4-寬直徑之上限值。最後,便可因此決定出增強型金字塔網路之ω-寬直徑。
Chen et al. proposed in 2004 a new hierarchy structure, called the enhanced pyramid network (EPM), by replacing each mesh in a pyramid network (PM) with a torus. Recently, some topological properties and communication on an EPM have been investigated or derived. Their measurement results indicate that an EPM is an attractive alternative to a PM. In order to evaluate reliability and fault tolerant ability, maximize parallelism and minimize transmission delay for fast parallel communication of an interconnection network, constructing node-disjoint paths and determining ?-wide diameters of the network are very important issues. Given two distinct nodes in an interconnection network, there may be many different containers between these two nodes. Establishing a ω-wide best-container between two given nodes and then computing ω-wide diameters of a κ-connected network are very difficult, where ω ≤ κ. Since connectivity of every enhanced pyramid network is 4, by Menger’s theorem and its variances, there are at least 4 node-disjoint paths between arbitrary two distinct nodes in an enhanced pyramid network. This work first computes upper bounds of 2-, 3- and 4-wide diameters of an n-layer enhanced pyramid network by providing novel algorithms for constructing 2-, 3- and 4-wide containers as short as possible between every two distinct nodes of the network. Second, build 2, 3 and 4 paths between two specific nodes whose lengths are at most the lengths of 2-, 3- and 4-best-containers and equal to upper bounds of 2-, 3- and 4-wide diameters of the n-layer enhanced pyramid network, respectively. Finally, ω-wide diameters of an EPM can then be determined.