Minimum connected dominating set and backbone of a random graph

DOI10.1088/1742-5468/AD4026MaRDI QIDQ6628838zbMATH OpenFDO

Authors Yusupjan Habibulla, Haijun Zhou

Publication date 29 October 2024

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

Full work available at URL https://doi.org/10.1088/1742-5468/AD4026

zbMATH Keywords

connected dominating setcycle-tree patternglobal constraintgraph backbonemessage passing

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Cites work

• Approximation algorithms for connected dominating sets
• Connected dominating set. Theory and applications
• From the physics of interacting polymers to optimizing routes on the London underground
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Hierarchical cycle-tree packing model for optimal K-core attack
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Information, Physics, and Computation
• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Primal-dual algorithms for connected facility location problems
• Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks
• Spin Glass approach to the feedback vertex set problem
• Statistical mechanics of the directed 2-distance minimal dominating set problem
• Statistical mechanics of the minimum dominating set problem
• The directed dominating set problem: generalized leaf removal and belief propagation

This page was built for publication: Minimum connected dominating set and backbone of a random graph

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