%0 Journal Article
%T Approximate Algorithms for Updating Single-Source Shortest Path Tree of Moving Target<br>移动目标单源最短路径树更新的近似算法
%A DONG Bin
%A LI Quan-Long
%A XU Xiao-Fei
%A SU Lu
%A <br>董彬
%A 李全龙
%A 徐晓飞
%A 宿陆
%J 计算机科学
%D 2006
%I 
%X This paper presents an approximate algorithm for updating the shortest path tree of moving target to avoid re-generate the whole tree. Based on the concept of Local map, the algorithm tries to update as few nodes as possible to reduce cost. The experimental results demonstrate that the new algorithm deserves good efficiency, approximation and scalabilities. Furthermore, we show how to reach the trade-off between efficiency and approximation.
%K Moving target
%K Single-source shortest path tree
%K Approximate algorithms
%K Local map<br>移动目标
%K 单源最短路径树
%K 近似算法
%K 局部图
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=8D025088EAE260D5&yid=37904DC365DD7266&vid=27746BCEEE58E9DC&iid=708DD6B15D2464E8&sid=8B59EA573021D671&eid=A1266CF37D675CF1&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=6