Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs

DOI10.1007/978-3-642-45030-3_14MaRDI QIDQ2872079zbMATH OpenOpenAlexFDO

Authors Marc Lelarge, Hang Zhou

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_14

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Spatial mixing and the connective constant: optimal bounds
• Spatial mixing and the connective constant: optimal bounds
• Random sampling for the monomer-dimer model on a lattice.
• Approximating the number of monomer-dimer coverings of a lattice.

Cited in

(2)

• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Matchings on infinite graphs

This page was built for publication: Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs

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