FPRAS for computing a lower bound for weighted matching polynomial of graphs
arXiv:cs/0703029
Abstract
We give a fully polynomial randomized approximation scheme to compute a lower bound for the matching polynomial of any weighted graph at a positive argument. For the matching polynomial of complete bipartite graphs with bounded weights these lower bounds are asymptotically optimal.
16 pages