摘要：已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.

摘要：分别总结了网络物理拓扑发现算法和网络逻辑拓扑发现算法两大类拓扑发现算法的基本思想和设计方法,分析了影响各算法性能的主要因素,并对今后网络拓扑发现算法的设计路线作了展望和提出了建议。对网络拓扑发现算法的设计者有较高的参考价值。