摘要：为满足复杂装备中某些关键系统的实时测试与诊断需求,在测试性设计过程中开展并行测试调度优化研究;针对测试任务之间关联关系复杂的实际情况,通过建立基于图染色理论的测试任务关系模型,实现了对系统资源冲突、死锁等问题的形式化描述,将并行测试调度优化转化为求解图的色数问题;并在求解图的色数问题过程中,利用改进的遗传算法逐步求解图的最大独立集,即可并行测试的测试任务子集,从而获得并行测试调度方案;最后,利用某实例对文章提出的并行测试任务调度建模及优化方法进行了验证,优化效果明显,证实了该方法对解决并行测试调度优化问题的有效性。

摘要：最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。

摘要：提出了将地图着色问题转化为顶点着色问题,然后把顶点着色问题转化为求最大独立集问题。最大独立集问题的解法采用改进的粘贴DNA计算,即全信息化的DNA粘贴计算。DNA粘贴计算设计了主链和存储链,而且在生物计算中采用并行处理。最后给出了一个实例,详细说明了地图着色问题的解法,得出了最终的解。

摘要：针对多信道无线网络下隐藏节点导致网络吞吐量下降的问题,提出了一种基于最大独立集(MIS)模型的多信道无线局域网介质访问控制(MAC)协议。该协议包括介质接入和信道分配2部分。其中,介质接入使用专用控制信道和发送请求/接收请求(RTS/CTS)握手机制;信道分配以MIS算法为基础,通过分布式算法实现。最后,利用OPNET仿真软件对该协议进行了分析和仿真。结果表明该协议可有效利用多信道资源,提升了无线网络性能,网络吞吐量比单信道协议提高了50%,同时降低了端到端延时。

摘要：对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.