Spin Glass approach to the feedback vertex set problem

DOI10.1140/epjb/e2013-40690-1zbMath1515.82158arXiv1307.6948OpenAlexW2010280523MaRDI QIDQ6176705

Hai-Jun Zhou

Publication date: 26 July 2023

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

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

zbMATH Keywords

statistical and nonlinear physics

Mathematics Subject Classification ID

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

Related Items

Circular convex bipartite graphs: feedback vertex sets, Underestimated cost of targeted attacks on complex networks, Optimal segmentation of directed graph and the minimum number of feedback arcs, Hierarchical cycle-tree packing model for optimal \(K\)-core attack, A spin glass approach to the directed feedback vertex set problem, Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics, The characteristics of cycle-nodes-ratio and its application to network classification, Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics, Efficient Network Dismantling via Node Explosive Percolation*, Minimal contagious sets in random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks
• Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
• Dynamics and control at feedback vertex sets. II: A faithful monitor to determine the diversity of molecular activities in regulatory networks
• A note on the cluster variation method.
• On the number of circuits in random graphs
• Partition function loop series for a general graphical model: free-energy corrections and message-passing equations
• Algorithm for counting large directed loops
• Information, Physics, and Computation
• Decycling graphs
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Decycling numbers of random regular graphs
• Loops of any size and Hamilton cycles in random scale-free networks
• Reducibility among Combinatorial Problems
• Observability of complex systems
• The complexity of theorem-proving procedures
• Statistical theory of superlattices
• Statistical theory of superlattices with unequal concentrations of the components
• On Ising's model of ferromagnetism
• A Theory of Cooperative Phenomena