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.
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
1 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
- $\begingroup$ The Lipton and Rose paper talks about solving sparse $Ax=b$. How do you get determinant from this? $\endgroup$Turbo– Turbo2025-02-23 04:31:04 +00:00Commented Feb 23 at 4:31