Statistical mechanics of the minimum dominating set problem
From MaRDI portal
Publication:888266
DOI10.1007/s10955-015-1220-2zbMath1329.82060arXiv1410.4607OpenAlexW1983157476MaRDI QIDQ888266
Yusupjan Habibulla, Jin-Hua Zhao, Hai-Jun Zhou
Publication date: 30 October 2015
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1410.4607
Random graphs (graph-theoretic aspects) (05C80) Approximation methods and heuristics in mathematical programming (90C59) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Percolation (82B43)
Related Items (9)
The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation ⋮ A local algorithm and its percolation analysis of bipartite z-matching problem ⋮ Two faces of greedy leaf removal procedure on graphs ⋮ Typical performance of approximation algorithms for NP-hard problems ⋮ Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics ⋮ Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński 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 ⋮ Observability transitions in clustered networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connected dominating set. Theory and applications
- Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
- Reconstruction on trees and spin glass transition
- Public goods in networks
- Minimal contagious sets in random regular graphs
- Statistical mechanics of complex networks
- Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Optimizing spread dynamics on graphs by message passing
- The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
- Information, Physics, and Computation
- On the hardness of approximating minimization problems
- Collective dynamics of ‘small-world’ networks
- Gibbs states and the set of solutions of random constraint satisfaction problems
- Statistical mechanics of the vertex-cover problem
- A dominating-set-based routing scheme in ad hoc wireless networks
This page was built for publication: Statistical mechanics of the minimum dominating set problem
