Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
From MaRDI portal
Publication:401479
DOI10.1016/j.tcs.2014.06.040zbMath1408.05124arXiv1208.3629OpenAlexW2795470862MaRDI QIDQ401479
Publication date: 27 August 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1208.3629
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for sampling algorithms for estimating the average
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Random generation of combinatorial structures from a uniform distribution
- Random matchings in regular graphs
- The statistical mechanics of strategic interaction
- A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
- Theory of monomer-dimer systems
- The Complexity of Counting in Sparse, Regular, and Planar Graphs
- Sublinear-Time Algorithms for Monomer-Dimer Systems on Bounded Degree Graphs
- Counting independent sets up to the tree threshold
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- Approximating average parameters of graphs
- Information, Physics, and Computation
- Matchings and walks in graphs
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Lee-Yang theorems and the complexity of computing averages
- Correlation Decay up to Uniqueness in Spin Systems
- Approximate Counting via Correlation Decay in Spin Systems
This page was built for publication: Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
