2023-11-26姚崇翔第二十三周周报

本周进度:

继续阅读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-边连通分量算法

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容