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

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