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

Simple item page
dc.creatorFriedland, Shmuel
dc.date2007-03-06
dc.date2007-04-12
dc.date.accessioned2026-07-07T07:56:13Z
dc.date.available2026-07-07T07:56:13Z
dc.descriptionWe 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.
dc.description16 pages
dc.identifierhttps://arxiv.org/abs/cs/0703029
dc.identifierhttp://arxiv.org/abs/cs/0703029
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/127231
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleFPRAS for computing a lower bound for weighted matching polynomial of graphs
dc.typetext

Files

Collections

arXiv