Statistical mechanics of the vertex-cover problem

DOI10.1088/0305-4470/36/43/028zbMath1077.68073arXivcond-mat/0307236OpenAlexW1978652044WikidataQ58001593 ScholiaQ58001593MaRDI QIDQ5696397

Alexander K. Hartmann, Martin Weigt

Publication date: 18 October 2005

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0307236

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Related Items (9)

Properties of atypical graphs from negative complexities ⋮ Statistical mechanics of the minimum dominating set problem ⋮ Two faces of greedy leaf removal procedure on graphs ⋮ What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO ⋮ Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics ⋮ Parallel tempering for the planted clique problem ⋮ Measuring instance difficulty for combinatorial optimization problems ⋮ Minimal vertex covers of random trees ⋮ Directed Dominating Set Problem Studied by Cavity Method: Warning Propagation and Population Dynamics

This page was built for publication: Statistical mechanics of the vertex-cover problem