Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
From MaRDI portal
Publication:3302870
DOI10.1088/1742-5468/AA8C1EzbMATH Open1457.82430arXiv1706.01064OpenAlexW2622526750MaRDI QIDQ3302870FDOQ3302870
Authors: Yusupjan Habibulla 
Publication date: 11 August 2020
Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1706.01064
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
- Title not available (Why is that?)
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Public goods in networks
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Spin Glass approach to the feedback vertex set problem
- Information, Physics, and Computation
- Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
- Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
- Reconstruction on trees and spin glass transition
- A dominating-set-based routing scheme in ad hoc wireless networks
- Statistical mechanics of the minimum dominating set problem
- Statistical mechanics of the vertex-cover problem
- Entropy of theK-Satisfiability Problem
- The directed dominating set problem: generalized leaf removal and belief propagation
Cited In (5)
- 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
- Directed dominating set problem studied by cavity method: warning propagation and population dynamics
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)
