咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Optimal deterministic broadcas... 收藏

Optimal deterministic broadcasting in known topology radio networks

在已知的拓扑学收音机网络的最佳的确定的广播

作     者:Kowalski, Dariusz R. Pelc, Andrzej 

作者机构:Univ Liverpool Dept Comp Sci Liverpool L69 7ZF Merseyside England Univ Quebec Dept Informat Gatineau PQ J8X 3X7 Canada 

出 版 物:《DISTRIBUTED COMPUTING》 (分布式计算)

年 卷 期:2007年第19卷第3期

页      面:185-195页

核心收录:

学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

主  题:broadcast deterministic algorithm radio network graph 

摘      要:We consider deterministic broadcasting in radio networks whose nodes have full topological information about the network. The aim is to design a polynomial algorithm, which, given a graph G with source s, produces a fast broadcast scheme in the radio network represented by G. The problem of finding a fastest broadcast scheme for a given graph is NP-hard, hence it is only possible to get an approximation algorithm. We give a deterministic polynomial algorithm which produces a broadcast scheme of length O(D + log(2) n), for every n-node graph of diameter D, thus improving a result of Gasieniec et al. (PODC 2005) [ 17] and solving a problem stated there. Unless the inclusion NP subset of BPTIME(n(O(log log n))) holds, the length O(D + log(2) n) of a polynomially constructible deterministic broadcast scheme is optimal.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分