A better constant-factor approximation for weighted dominating set in unit disk graph
贝壳书屋
贝壳书屋
贝壳书屋 A better constant-factor approximation for weighted dominating set in unit disk graph 电子书下载

A better constant-factor approximation for weighted dominating set in unit disk graph 电子书下载

admin A+ A- 该资源由用户: 百花庆洲 上传  举报不良内容

书名：A better constant-factor approximation for weighted dominating set in unit disk graph

A better constant-factor approximation for weighted dominating set in unit disk graph.jpg

This paper presents a (10 + ε)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio 6 + ε (ε is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4.

尊敬的读者：
欢迎您访问我们的网站。本站的初衷是为大家提供一个共享学习资料、交换知识的平台。每位用户都可以将文件上传至网盘并分享。
然而，随着用户上传的资料增多，我们发现部分不宜或版权问题的书籍被分享到了本站。 为此，我们已经关闭了分享入口，并进行了多次书籍审查，但仍有部分内容未能彻底审查到位。
在此，我们恳请广大读者与我们共同监督，如发现任何不宜内容，请 点击此处 进行举报，我们会第一时间处理并下架相关内容。
希望我们能共建一个文明社区！感谢您的理解与支持！

better constant factor approximation weighted dominating set unit disk graph

猜你喜欢

友情链接

贝壳书屋 © All Rights Reserved.  
关于我们| 联系我们| 留言|