算法优化下 Möbius 立方体的交叉数边界研究

本文主要探讨了Möbius立方体（Mobius cubes, MQn）的交叉数问题。Möbius立方体是一种在多处理器系统、并行计算机架构以及大规模集成电路等高性能计算领域广泛应用的直连网络拓扑结构。直连网络因其简单高效的通信特性而备受重视，尤其是在需要低延迟和高带宽的现代计算环境中。 作者闫晓霞和杨元生针对Möbius立方体的图形表示，提出了一个计算机算法来寻找平面图中的良好绘制方法。他们的研究旨在获取MQn的更优上界，即最小化其边在平面上交叉的次数，这是衡量网络性能的一个关键指标。通过严谨的理论分析和数值优化，他们试图优化网络设计，提高整体系统的效率和性能。 在论文的开端，作者明确了研究背景，指出交叉数在图论中的重要性，并声明他们的工作得到了国家自然科学基金（NSFC）的支持（项目号：60973014和60803034），同时还有国家自然科学基金青年科学基金项目（SRFDP，编号200801081017）。两位作者的简介也揭示了他们的专业背景，闫晓霞博士专攻图论，而杨元生教授则为通讯作者，同样专注于图论领域的研究。 在论文的核心部分，作者详细介绍了交叉数的定义，即对于无环无多重边的有限无向图G，cr(G)是所有可能绘制方式中边交点最少的数目。他们关注的是如何通过算法手段找到MQn在平面上的最优布局，以便减少交叉，这将直接影响网络的物理实现成本和信号干扰问题。 值得注意的是，本文不仅提供了上界估计，还给出了MQn的下界，这展示了对问题的全面理解，以及对网络性能极限的探索。这种研究对于优化并行系统的设计，提升系统性能和降低复杂性具有重要意义。 这篇首发论文通过对Möbius立方体的细致研究，为理解这类直连网络的图形表示及其优化提供了新的见解和技术手段，为相关领域的工程师和研究人员提供了有价值的信息和工具。