计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2013年
z1期
299-301,310
,共4页
可达性%K-Reach索引%优化算法
可達性%K-Reach索引%優化算法
가체성%K-Reach색인%우화산법
Rechibility%K-Reach index%Algorithm optimization
基于经典网络可达性问题的k可达性问题对于无线网络、社交网络等新型网络具有重要意义.最新提出的K-Reach[1]可以快速地计算任意两个顶点之间是否存在长度小于为女的路径.注意到随着K-Reach索引的逐步建立,已经计算过的顶点包含其所有可达顶点的路径信息.因此,提出一种改进的K-Reach索引创建算法,其充分利用了这些路径信息,避免了重复访问大量顶点,从而提升了算法效率.通过对不同实际数据进行的实验表明,改进算法所用时间明显小于原始算法.
基于經典網絡可達性問題的k可達性問題對于無線網絡、社交網絡等新型網絡具有重要意義.最新提齣的K-Reach[1]可以快速地計算任意兩箇頂點之間是否存在長度小于為女的路徑.註意到隨著K-Reach索引的逐步建立,已經計算過的頂點包含其所有可達頂點的路徑信息.因此,提齣一種改進的K-Reach索引創建算法,其充分利用瞭這些路徑信息,避免瞭重複訪問大量頂點,從而提升瞭算法效率.通過對不同實際數據進行的實驗錶明,改進算法所用時間明顯小于原始算法.
기우경전망락가체성문제적k가체성문제대우무선망락、사교망락등신형망락구유중요의의.최신제출적K-Reach[1]가이쾌속지계산임의량개정점지간시부존재장도소우위녀적로경.주의도수착K-Reach색인적축보건립,이경계산과적정점포함기소유가체정점적로경신식.인차,제출일충개진적K-Reach색인창건산법,기충분이용료저사로경신식,피면료중복방문대량정점,종이제승료산법효솔.통과대불동실제수거진행적실험표명,개진산법소용시간명현소우원시산법.
