ECQ网络中嵌入哈密顿圈的高效算法研究

摘要

网络的哈密顿性质在信息通信领域中具有重要的应用。具有哈密顿性质的网络能够高效率地进行线性或循环通信。交换交叉立方体(ECQ)网络是一种性能优良的互连网络。它既有较小的网络直径,又具有较低的构造成本。如果在ECQ网络的多播路由算法中使用哈密顿性质,则能够有效地减少ECQ网络通信中的死锁和拥塞。对ECQ网络中嵌入哈密顿圈的构造算法进行了研究。首先,给出了当s≥3和t≥3时,ECQ网络上从任意节点出发构造哈密顿圈的算法。然后,给出了当1≤s≤2时,ECQ网络上哈密顿圈的构造算法。最后,通过仿真试验验证了算法的正确性、有效性和高效性。本研究结果可为ECQ网络哈密顿性质的应用提供重要的理论依据。