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$
9
$\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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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