Authors
Mohsen Bayati, David Gamarnik, Dimitriy Katz, Chandra Nair, Prasad Tetali
Publication date
2007/6/11
Book
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
Pages
122-127
Description
We construct a deterministic fully polynomial time approximationscheme (FPTAS) for computing the total number of matchings in abounded degree graph. Additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(O(√n log2n)),where n is the number of vertices.
Our approach is based on the correlation decay technique originating in statistical physics. Previously thisapproach was successfully used for approximately counting thenumber of independent sets and colorings in some classes of graphs [1, 24, 6].Thus we add another problem to the small, but growing, class of P-complete problems for whichthere is now a deterministic FPTAS.
Total citations
2006200720082009201020112012201320142015201620172018201920202021202220232024152107109917715978312493
Scholar articles
M Bayati, D Gamarnik, D Katz, C Nair, P Tetali - Proceedings of the thirty-ninth annual ACM symposium …, 2007