7
$\begingroup$

I know through Kirchoff's Theorem, one can calculate the number of spanning trees via the determinant of a Laplacian. This has complexity $O(N^{2.373}$). I was wondering if anyone was aware of a method which computes this faster, at least for planar graphs.

$\endgroup$
8
$\begingroup$

The determinant of matrices whose support corresponds to incidence matrices of planar graphs (this includes the Laplacian matrix of a planar graph, or more precisely its cofactors) can be calculated in $O(n^{1.5})$ with the algorithm given in

R.J. Lipton, D. Rose, R.E. Tarjan Generalized nested dissection SIAM J. Numer. Anal., 16 (1979), pp. 346-358

which uses the planar separator theorem (see also nested dissection).

Another algorithm that runs in $O(n^2)$ but sometimes more efficient to implement is the one based on delta-wye graph reduction (a set of combinatorial substitution rules on the graph) given in

C.J. Colbourn, J.S. Provan, D. Vertigan A new approach to solving three combinatorial enumeration problems on planar graphs Discrete Appl. Math., 60 (1995), pp. 119-129

$\endgroup$
  • $\begingroup$ Follow up question, do you know if these methods have large coefficients? I’m trying to figure out if Wilson’s algorithm is much faster than them on 400 vertex graphs, or if they would be roughly as fast as one another. $\endgroup$ – Zachary Hunter Dec 29 '18 at 5:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.