关于SPS-图的一个充分条件

如果图中的一条路不是其他任何路的子路,则称这条路为该图的一条极大路。图G的路谱指的是G中所有极大路的长度构成的集合,记为ps(G)。对于一个阶为n的图G,如果存在一个正整数s(G)使得ps(G)={s(G),s(G)+1,…,n-1},则称G为一个SPS-图。本研究证明了对于任意的2-连通图G,如果G中任何导出子图都不与K1,3或P5同构,则G是一个SPS-图或者是一类路谱特殊的图。

关于带有有向图的G-非扩张映射的有限步SP-迭代方法的收敛性分析

在带有有向图的一致凸的Banach空间中证明了有限个G-非扩张映射的公共不动点的SP-迭代方法的强收敛定理和弱收敛定理,并给出数值例子论证该方法的优点.

无蜂窝大规模MIMO系统信道估计中基于加权图的叠加导频分配

针对无蜂窝大规模多输入多输出(cell-free massive multiple-input multiple-output, CF-mMIMO)系统信道估计中导频污染问题,提出了基于加权图的叠加导频(superimposed pilot, SP)分配方案。首先分析导频污染对SP信道估计的影响,引入一种全新度量表示用户间潜在导频污染程度;其次根据接入点与用户间大尺度衰落系数完成用户加权干扰图构建,将系统吞吐量最大化问题转化为有容量最大k切割问题求解;最后采取顶点交换局部搜索算法实现SP次优分配。仿真结果表明:本文方案能够有效地改善SP信道估计误差以及系统吞吐量。

系列平行图的边色数

Vizing( 1 96 4年 )和Gupta( 1 96 6年 )各自独立地证明了边着色中的重要定理 :对任何简单图G ,有χ′(G) =Δ或 χ′(G) =Δ + 1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质 。

基于因子图的同频数字混合信号单通道盲分离

本文针对复杂编码下同频数字调制混合信号单通道盲分离问题,构建了利用因子图设计盲分离算法的统一框架。通过将和积消息传递算法与ECM参数估计算法有机地结合,提出一种基于因子图的编码辅助同频混合信号单通道盲分离算法。确定了在最大似然准则下混合信号同步参数的估计式。利用广义分配率准则,为存在码间干扰的混合信号建立了合理的因子图模型,得到了符号序列的后验概率估计式。仿真结果表明,本文提出的算法不仅能够对卷积码混合信号取得较好的分离性能,还能有效实现对LDPC码等复杂编码混合信号的参数和序列的联合估计。

串并有向图的判定算法及应用实例

串并有向图常作为单机排序问题研究中的约束条件,针对目前并未有一个确切算法判定任意一个有向图是否为串并有向图的问题,提出了串并有向图的判定算法H。算法H利用数学中的递归法,对有向图进行逐层递归分解,对分解结果进行分析判定该有向图是否为串并有向图。结果表明:该问题能在多项式内可解,属于组合优化中的P问题。算法H普遍适用于任意有向图,解决了串并有向图的判定问题。

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。