FPRAS for computing a lower bound for weighted matching polynomial of graphs

Shmuel Friedland

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 polyn…