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

2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/127231We 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 pagesComputational ComplexityDiscrete MathematicsFPRAS for computing a lower bound for weighted matching polynomial of graphstext