本周进度:
继续阅读Construction of Quality Virtual Backbones with Link Fault Tolerance in Wireless Sensor Networks。
看明白了2E-blocks的计算算法,这是本篇文章的关键及创新点,利用了点染色及ID进行计算。
看明白了相关4个引理证明及近似比证明。
引理1 如果G[S_j^u]中TC分解的分量都是2-连通的,那么G[S_j^u]就是2-连通的。
引理2 算法最后输出的每一组Eblck_ID()相同的点都是2E−blocks
引理3 算法最后输出结果包含了G[S]中所有2E−blocks
引理4 G中必定存在路径L_k(S_0∪connector)(k≤2)连接两个不同的2E−blocks
遇到问题:
下周目标:调研3-边连通分量算法