I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger Markov process. Though I am aware of theoretical methods for both of these tasks, I was unable to find even rough estimates to complexity coefficients for any process.
My question is, for graphs with 400 vertices, could anyone hazard a guess as to how much faster it is to create a random spanning trees than to count possible spanning trees?
I believe Wilson's algorithm is fastest to create trees uniformly at random. For methods to count spanning trees, there are a few methods, detailed here. (I should note, for the first method, involving matrix factoring, I'm only worried about the time it takes to factor everything, and not the numbering which comes beforehand, because the numbering can be reused. The reason for this is these processes are occurring on subgraphs of a larger 2800 vertex graph, so we can number once and be done with that.)