1.6k citations · 6.9k across the 61 of their papers we have counts for
4 papers · 1 filter
Statistical mechanics of combinatorial auctions
Tobias Galla, Michele Leone, Matteo Marsili +3
Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Tran…
Message passing for vertex covers
Martin Weigt, Haijun Zhou
Constructing a minimal vertex cover of a graph can be seen as a prototype for a combinatorial optimization problem under hard constraints. In this paper, we develop and analyze mes…
Sudden emergence of q-regular subgraphs in random graphs
Marco Pretti, Martin Weigt
We investigate the computationally hard problem whether a random graph of finite average vertex degree has an extensively large -regular subgraph, i.e., a subgraph with all vert…
Introduction to graphs
Alexander K. Hartmann, Martin Weigt
Graph theory provides fundamental concepts for many fields of science like statistical physics, network analysis and theoretical computer science. Here we give a pedagogical introd…