FPRAS for computing a lower bound for weighted matching polynomial of graphs
Abstract
Description
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
16 pages