Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics

DOI10.1088/1742-5468/AA8C1EMaRDI QIDQ3302870zbMATH OpenOpenAlexFDO

Authors Yusupjan Habibulla

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.01064

Mathematics Subject Classification ID

Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: The minimal dominating Set (MDS) problem is a prototypical hard combinatorial optimization problem. Two years ago we studied this problem by cavity method. Although we get the solution of a given graph, which gives very good estimation of minimal dominating size, but we don't know whether we get the ground state solution and how many solutions exist in the ground state. For this purpose, last year we continue to develop the one step replica symmetry breaking (RSB) theory to find the ground state energy of the MDS problem. Finally we find that 1) The MDS problem solution space has both condensation transition and cluster transition on regular Random (RR) graph and we prove this by simulated annealing dynamical process. 2) We developed zero temperature Survey Propagation (SP) algorithm on ER graph to estimate the ground state energy and to get Survey Propagation Decimation (SPD) algorithm with good results same as BPD algorithm.

Recommendations

• Statistical mechanics of the minimum dominating set problem
• Directed dominating set problem studied by cavity method: warning propagation and population dynamics
• FINDING MINIMA IN COMPLEX LANDSCAPES: ANNEALED, GREEDY AND RELUCTANT ALGORITHMS
• Simulated annealing and the mapping problem: A computational study
• Simulated annealing for single minimum optimization problems
• Towards the analysis of the simulated annealing method in the multiextremal case
• Solving the generalized minimum spanning tree problem with simulated annealing

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• A dominating-set-based routing scheme in ad hoc wireless networks
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Entropy of theK-Satisfiability Problem
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
• Public goods in networks
• Reconstruction on trees and spin glass transition
• Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
• Spin Glass approach to the feedback vertex set problem
• Statistical mechanics of the minimum dominating set problem
• Statistical mechanics of the vertex-cover problem
• The directed dominating set problem: generalized leaf removal and belief propagation
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(5)

• Directed dominating set problem studied by cavity method: warning propagation and population dynamics
• Statistical mechanics of the minimum dominating set problem
• Two faces of greedy leaf removal procedure on graphs
• Minimum connected dominating set and backbone of a random graph
• Statistical mechanics of the directed 2-distance minimal dominating set problem

This page was built for publication: Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302870)