Skip to main content
MathOverflow

Return to Question

added the tag spanning-tree
Link
edit approved Oct 25, 2018 at 15:59
F. C.
edit approved Oct 25, 2018 at 15:59
F. C.
  • 3.7k
  • 21
  • 32
top-level tag and tidy
Source Link
Ben Barber
Ben Barber
  • 4.7k
  • 2
  • 27
  • 39

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}$$O(N^{2.373}$). I was wondering if anyone was aware of a method which computes this faster, at least for planar graphs.

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

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.

Source Link
Zach Hunter
Zach Hunter
  • 3.5k
  • 2
  • 12
  • 24

Counting spanning trees of a planar graph

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