Spectral sparsification and spectrally thin trees

[摘要] We provide results of intensive experimental data in order to investigate the existence of spectrally thin trees and unweighted spectral sparsifiers for graphs with small expansion. In addition, we also survey and prove some partial results on the existence of spectrally thin trees on dense graphs with high enough expansion.

[发布机构] Massachusetts Institute of Technology