English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The L-distance (especially the 2-distance) minimal dominating set (MDS)problem is widely considered in various dominating set problems. Recently, westudied the regular dominating set problem using the cavity method anddeveloped two algorithms (belief propagation decimation and survey propagationdecimation) to estimate the solution of a given graph, resulting in very goodestimations of the minimal dominating size. This paper describes thedevelopment of spin glass theory to study the 2-distance MDS problem. First, weshow that the belief propagation equation does not converge when the inversetemperature $\beta$ is greater than a certain threshold value on both regularand Erdos--Renyi random networks. Second, we find that the entropy density isequal to zero at finite inverse temperature on regular random graphs when thenode degree is from 3--9, and on Erdos--Renyi random networks when the nodedegree is from 4.2--10.4; the entropy density is positive in all other cases.This result is proved using a dynamical simulated annealing process. Third, theresults of replica symmetry theory are shown to be in agreement with those ofthe belief propagation algorithm, and the results of the belief propagationdecimation algorithm are found to be better than those of the greedy heuristicalgorithm.

Two-distance minimal dominating set problem studied by statistical mechanics and simulated annealing