The complexity of approximating the matching polynomial in the complex plane
We study the problem of approximating the value of the matching polynomial on graphs with edge parameter γ, where γ takes arbitrary values in the complex plane. When γ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of γ,...
| Príomhchruthaitheoirí: | , , , |
|---|---|
| Formáid: | Journal article |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Association for Computing Machinery
2021
|