网络流量的有效测量方法分析

把网络流量的有效测量问题抽象为求给定图G=(V,E)的最小弱顶点覆盖集的问题.给出了一个求最小弱顶点覆盖集的近似算法,并证明了该算法具有比界2(lnd+1),其中d是图G中顶点的最大度.指出了该算法的时间复杂性为O(|V|²).     

基于原始对偶方法求解网络流量监测集算法

考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比界为2.进一步分析了求解基于最大流划分的最小弱顶点覆盖集的近似算法.     

全光双向网络中的波长转换

在许多光学路由中,对于给定一组通讯路的集合,必须对有公共边的路安排相同的波长.为了充分利用光学的带宽,目的是安排尽量少的波长数.但有时候也考虑使用波长转换器. 如果一个顶点安装转换器,任何经过这个顶点的路都可以改变其波长.因此在某些顶点安装波长转换器后可以将波长的数目减少到一个拥塞界,因此,Wilfong和Winkler定义了一个顶点集 S,在S上安装转换器后,任何路集都可以分配数目等于拥塞界的波长,这样的集合S被称为充分集.研究在双向网络中的最小充分集问题,并把他转化为最小顶点覆盖问题.对此问题给出几个算法.     

一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法

二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为：当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖（ku,kl）时,对任意给定的近似率δ=1＋ε〉1,一定可以找到一个受约束近似点覆盖（ku,kl）,对应的近似率为max{ku^＊/ku,kl^＊/kl}≤1＋ε,整个近似算法的运行时间复杂度为O（22/ε）。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案（polynomial time approximation scheme,PTAS算法）。     

一种求解顶点覆盖问题的混合遗传算法

顶点覆盖问题是一个NP难问题,在排序、计算机网络等现实生活中有许多的应用。使用基本遗传算法进行搜索时,存在着局部搜索能力较弱的不足,本文提出了一种新的求解最小顶点覆盖问题的混合遗传算法,将基本遗传算法与局部优化策略相结合,改善遗传算法的局部搜索能力,加快求解该问题的速度。对几种典型无向图的实验证实了新方法的有效性,其整体性能优于现有的一些顶点覆盖问题遗传算法。     

On the parameterized vertex cover problem for graphs with perfect matching

A vertex cover of an n-vertex graph with perfect matching contains at least n/2 vertices.In this paper,we study the parameterized complexity of the problem vc-pm*that decides if a given graph with perfect matching has a vertex cover of size bounded by n/2+k.We first present an algorithm of running time O*(4k)for a variation of the vertex cover problem on K¨onig graphs with perfect matching.This algorithm combined with the iterative compression technique leads to an algorithm of running time O*(9k)for the problem vc-pm*.Our result improves the previous best algorithm of running time O*(15k)for the vc-pm*problem,which reduces the problem to the almost 2-sat problem and solves the latter by Razgon and O’Sullivan’s recent algorithm.     

控制集与部分控制集问题的原始-对偶算法

图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为△＋1的近似算法（△为图中顶点最大度）。     

改进的最优顶点覆盖贪心边近似算法

最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

一种求解平面图的最小顶点覆盖算法

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

基于核心化技术的点覆盖改进算法

点覆盖是一个著名的NP难解问题,在通信网络和生物信息学等领域具有重要应用。针对点覆盖的研究主要集中在启发式或近似算法,其主要不足是无法实现全局最优。核心化是处理难解问题的一种新方法。提出融合启发式操作和核心化操作的算法框架,利用核心化技术进行点覆盖启发式算法优化。核心化操作挖掘出全局最优的顶点集,而启发式操作改变网络拓扑,使下一轮核心化操作能够继续,两者交叉执行实现解精度优化。实验结果表明,提出的算法在不同网络中均能实现不同程度的优化,在几乎所有稀疏网络实例中获得了最优解。     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

团图点删除问题的近似算法

针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。     

一种混合化学反应优化算法求解最小顶点覆盖问题

最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。论文针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学化反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。     

基于邻接矩阵的网络流量检测点设置算法

在研究网络流量的有效测量问题时,考虑网络节点的流守恒,把网络流量监测点问题抽象为无向图的最小弱顶点覆盖问题,这是一个NP难的问题.基于图论中邻接矩阵的概念,提出一个近似算法,通过重复删除邻接矩阵中所有行元素之和不超过1的节点对应的行和列,得到最小弱顶点覆盖集.在此基础上通过预先递归去除无向图中1度节点,满足任意节点度数都大于或等于2的最小弱顶点覆盖问题求解条件,并将递归节点作为该近似算法的入口点.仿真实验表明,与现有算法相比,新算法具有更好的性能,能够发现更小的弱顶点覆盖集.     

模糊环境下的最小权顶点覆盖问题*

最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。