高级检索

    Mbius立方体互连网络上的圈嵌入算法

    A CYCLE EMBEDDING ALGORITHM ON MBIUS CUBE INTERCONNECTION NETWORKS

    • 摘要: 图嵌入技术是研究多处理器互连网络模拟其它网络的能力的重要技术.文中讨论了近年提出的一类互连网络——Mobius立方体上的圈嵌入性质.Mobius立方体是超立方体的变型,它们具有一些比超立方体更优越的性质,如n维Mobius立方体Mn的直径大约是n维超立方体的一半,其期望距离大约是n维超立方体的23等.文中证明了Mobius立方体另一个比超方体优越的性质,即任一长度为l(4≤l≤2n)的圈能以扩张l嵌入n维Mobius立方体Mn(n≥2),并给出了构造过程,从而也证明Mn对环网络的模拟能力比超立方体的高(超立方体不含奇长圈).

       

      Abstract: The graph embedding is an important technique to study the capability of multiprocessor interconnection networks simulating other networks. The property of cycle embedding of a kind of interconnection networks recently introduced——the Mbius cubes is discussed. They are hypercube variants which give better properties than hypercubes. For example, the diameter of the n dimensional Mbius cube M n is about one half that of the n dimensional hypercube, the expected distance of M n is about two thirds that of the n dimensional hypercube, etc..It is proved that the Mbius cubes have another better property than hypercubes, i.e., any cycle of length l(4≤l≤2 n) can be embedded into the n dimensional MAKo¨D4bius M n(n≥2) and gives a constructing procedure, and also proves that the capability of M n’ s simulating ring networks is higher than that of the n dimensional hypercube (hypercubes do not contain odd cycles).

       

    /

    返回文章
    返回