基于节点度数和跳数的网络检测点选取算法

为解决网络检测点的选取问题,基于网络节点度数和跳数信息,提出一种动态网络检测点选取算法. 该算法使用三元组信息标记网络节点,并通过比较和替换节点的三元组信息,根据三元组信息中参数N的不同取值,分别完成流量和延迟两种网络检测点的选取. 仿真结果表明,新算法不需要维护网络拓扑的全局信息,能够有效解决网络流量检测点和网络延迟检测点的选取问题.     

分层算法求解竞赛图上的最小弱顶点覆盖

竞赛图上的弱顶点覆盖问题是一个NP困难问题,本文先定义了竞赛图上的势加权函数,然后利用分层技术给出了一个求解竞赛图最小弱顶点覆盖问题的近似算法,并证明了此近似算法的近似度为3     

Pythagorean模糊信息系统属性约简的图论方法

信息系统中,属性约简是知识发现问题的一个研究热点,能达到发掘并简化知识的目的。目前已有很多利用辨识矩阵来进行属性约简的研究,但是当数据维数较大时,算法复杂度往往很大。利用加权欧几里得距离来定义二元关系及辨识矩阵,利用信息系统的约简与生成图的最小顶点覆盖等价的关系,将辨识矩阵求解约简的问题转化为求解生成图中最小顶点覆盖的问题,并给出了Pythagorean模糊信息系统中属性约简的算法;在此基础上,利用基于加权欧几里得距离的相似关系,定义了Pythagorean模糊决策信息系统的辨识矩阵,并给出了用最小顶点覆盖的方法求约简算法,最后利用实例验证了算法的有效性。     

点集在凸多边形内外判断算法的拓扑映射方法

提出了基于拓扑映射的点集在凸多边形内外判断的新算法。首先做凸多边形各顶点的拓扑映射点,然后将每个检测点的映射点与其插值,从而只需判断该点和凸多边形其中一条边的关系就可得出其与凸多边形的位置关系。     

次模函数近似算法求最小弱顶点覆盖

求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度。     

最小顶点覆盖问题的一个近似算法

最小顶点覆盖是图论中的一个重要概念，它是一个NP难的问题．给出了一个求解最小顶点覆盖的近似算法，与现有算法相比具有更优的性能比。     

基于半定规划的多约束图划分问题

提出一种递归的二分算法,用于求解带顶点权重约束的图划分问题.首先利用内点法求解不加顶点权重约束的半定规划松弛模型,然后利用超平面舍入算法得到满足顶点权重约束的初始可行解,再进一步设计启发式算法对初始可行划分进行局部改进,以得到更优的划分结果.实验结果表明,所设计的算法可在较短时间内得到多约束图划分问题的高质量解.     

超图的最短路径算法

从超图的强同构引出保持超图顶点间超邻接性的点同构,定义超图的邻接矩阵和赋权超图的权矩阵,并在此基础上得到了求解超图任意顶点间最短路径和求解超图直径的推广Floyd算法.最后通过实例验证了算法的可行性,并与李春明在1994年得到的结果进行比较,得出算法的复杂度为O(n3),该算法是一个有效算法.     

交互式马尔科夫链上弱模拟关系的计算

对交互式马尔可夫链模型(IMCs)上的弱模拟前序关系的计算算法进行讨论.在IMCs上判断弱模拟关系时,重点对概率转移关系进行弱模拟前序关系的判断,同时考虑内部动作对系统的影响.通过引入适当的变量,将IMCs上弱模拟定义中的马尔可夫转移条件转化为求解一个线性规划问题的解.利用该线性规划问题的数值求解方法,可在多项式时间内求得该线性规划问题的解.从而得到判定IMC上两个进程是否弱模拟的多项式时间算法.     

应用思维进化计算求解顶点着色问题

应用思维进化计算求解顶点着色问题,给出求解给定图的色数、最小着色的算法。介绍了顶点着色问题的编码与解码方法、特征、信息矩阵的概念,从而应用思维进化计算的趋同和异化求解该问题。实验结果表明该算法是求解顶点着色问题的一种新的有效算法。     

被动测试中网络监测问题

研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况．先把该问题归结为图的顶点覆盖问题，它是一个NP完全问题；接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解，并给出了树结构上带权顶点覆盖问题的线性时间算法；然后在已有的一个近似比为2的算法基础上。结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法，最后用实验验证了改进算法能使观察者数目减小20％左右．     

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.     

城市物流配送的二阶段启发式算法

针对城市物流配送的特点,将空间聚类算法与蚁群算法相结合运用到路径规划中,提出了一个基于交通网络的VRP二阶段解法.以带权图描述城市交通路网,利用交通网络中各个结点间的距离关系和结点的需求量,以配送车辆的容量为聚类的约束,通过多次迭代将所有结点聚集成相互独立的多个簇.选择簇间相似性最小的聚类,利用蚁群算法,根据簇之间和簇内结点间的距离关系,分两次规划配送路径,最终得到配送中心到所有结点的配送路径.该算法通过聚类降低系统复杂度,缩短了蚁群搜索时间,具有较快的速度.最后用一个仿真实例验证二阶段算法的有效性.     

基于测量聚类的网络拓扑推断算法

为了减少基于端到端时延的拓扑推断算法中产生的测量流量,根据网络中端到端时延的特点,提出了一种测量聚类算法和两阶段拓扑推断算法.测量聚类算法在测量时首先粗略测量网络节点的端到端时延,根据时延对节点进行聚类,然后根据节点的聚类测量节点对的端到端时延并计算节点相关性,最后通过两阶段拓扑推断算法推断网络拓扑结构.理论证明了测量聚类算法能够有效减少测量产生的测量流量并通过NS2进行了仿真,仿真结果表明测量聚类算法和两阶段拓扑推断算法在有效减少测量流量的情况下能够正确地推断网络的拓扑结构.     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

奖励收集顶点覆盖问题的一个2-近似算法

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。     

基于区域扩展的绿色业务量疏导算法

针对全光网络中传统绿色业务量疏导算法阻塞率高的性能缺陷,提出一种全光网络中基于区域扩展的绿色业务量疏导算法。该算法基于W+5分层图模型,生成一个仅包含部分网络节点的区域性辅助图,通过灵活扩展辅助图的方式,寻找最佳路径,避免了形成过长路由。仿真结果表明,与传统绿色业务量疏导算法相比,基于区域扩展的绿色业务量疏导算法能够有效地降低业务阻塞率,并且在高负载的情况下,网络的平均功耗最低。     

车联网中种时间约束的数据广播算法简

为解决车联网中时间约束条件下的数据广播问题,将该问题规约为二分图的约束最小顶点覆盖问题。证明该问题是NP-Hard问题,并提出一种启发式的数据广播算法。实验表明,相对于传统的路由算法,该算法充分考虑节点的联系概率及影响力,对于路由的包投递率和平均数据包端到端延时都有较大提升。     

基于网络流的多管制扇区通行能力

管制扇区间的通行能力问题通常是基于管制员的极限工作负荷、各种动态因素或者特殊航路点、航路交叉点的通行能力达到最优的情况进行研究,缺少对多扇区网络的整体地评估与计算。为了解决该问题,根据有向图理论以扇区为节点,以连接扇区的航路航线为边建立多扇区网络模型,选取华北飞行情报区的部分扇区进行仿真。首先,通过最大流算法求解出该网络模型的最大流为76.7架/h。其次,根据网络流仿真结果计算出各条边、各个节点的流容比,通过比较分析得出限制扇区网络通行能力的繁忙航路以及繁忙扇区。最后,通过灵敏度分析计算删除不同节点后网络模型的通行能力的变化,进而为扇区通行能力的优化提供了建议和参考。