There are many algorithms that address the MST problem, from classical (Boruvka, Prim, Kruskal), optimal (Pettie et al.) to their distributed variants (Bader et al.).

However, I fail to find any references to algorithms that might use spectral properties to algebraically arrive at a suitable representation of the MST (e.g. the set of edges, the adjacency or Laplacian matrix of the MST).

Are there any such algorithms or rationales (proofs) why they don't exist?


Your Answer

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

Browse other questions tagged or ask your own question.