一种高效的动态图最大加权独立集求解算法

独立集是图中顶点集的子集,该子集中的顶点之间不存在边。最大加权独立集是权值总和最大的独立集。最大加权独立集可以用来解决资源分配等问题,对于科学研究、商业应用等有重要作用。对于动态图上的最大加权独立集问题,现有研究并未给出合适的解决方案,本文针对此问题,提出支持高效更新的近似算法LSWTwo,当更新操作发生时,该算法考虑到受影响的点是距离为2范围内的点,因此,通过只处理该范围的点,可避免对最大加权独立集的重新搜索,提升更新操作的效率。最后,在多个真实数据集上进行比较,实验结果验证了LSWTwo算法的高效性。

OFDM中继系统中能效优化的资源联合分配算法

在协作正交频分复用系统中,合理的资源分配对于提高系统性能具有重要的意义。针对中继、子载波和功率的联合分配,对最大化系统能效为目标的分配算法进行研究,提出了一个最低容量限制下的最大能效次优化资源联合分配算法(JRAA,joint resource allocation algorithm)。该算法使用冲突图表示系统资源冲突关系,根据冲突图的最大独立集结果进行资源分配。经过仿真验证,该资源分配算法实现了中继一子载波和功率的联合分配,在能效性能方面优于现有的算法。