Randomized Approximation Schemes for the Tutte Polynomial and Random Clustering in Subdense and Superdense Graphs

Mathias Hauptmann, Ronja Tiling

Extending the work of Alon, Frieze abnd Welsh, we show that there are randomized polynomial time approximation schemes for computing the Tutte polynomial in subdense graphs with an…