Statistical mechanics of the directed 2-distance minimal dominating set problem |
| |
Authors: | Yusupjan Habibulla |
| |
Institution: | School of Physics and Technology, Xinjiang University, Sheng-Li Road 666, Urumqi 830046, China |
| |
Abstract: | The directed L-distance minimal dominating set (MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi (ER) random graph and regular random (RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation (BP) algorithm does not converge when the inverse temperature β exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds 3.3; there is no entropy transition point (or $\beta =\infty $) in other circumstances. Third, the results of the replica symmetry (RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm. |
| |
Keywords: | directed 2-distance minimal dominating set belief propagation regular random graph ER random graph belief propagation decimation |
本文献已被 万方数据 等数据库收录! |
| 点击此处可从《理论物理通讯》浏览原始摘要信息 |
| 点击此处可从《理论物理通讯》下载免费的PDF全文 |
|