.png){kind=icon}
返回
An Algorithm to Evaluate the Spectral Expansion
.png){kind=icon}
PRE
AI
DOI：10.1007/s40840-025-01984-5.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
假设X是一个阶数为n的有限阶连通(p + 1)-正则无向图。设A表示X的邻接矩阵。设lambda 1 = p + 1 > lambda 2 >= lambda 3 >= ... >= lambda n表示A的特征值。根据Cheeger不等式和Alon-Boppana定理，当n足够大时，若mu(X) = p^(-1/2) max |lambda(i)| (2 <= i <= n)接近2，则X的边膨胀和谱膨胀会很高。当参数p较低且边膨胀和谱膨胀较高时，图X是一个好的展开器（expander）。好的展开器在计算机网络、纠错码和概率算法中具有显著应用。本文中，以输入A和一个实数epsilon > 0，我们设计了一个算法，用于在O(n ω log log(1+epsilon) n)时间内估计mu(X) <= 2 + epsilon，其中ω是矩阵乘法的指数。
Keyword:
Dynamic programming
Geodesic cycle
Ihara zeta function
Spectral expansion
期刊
B
IF:
1.2
论文数:
143
被引数:
0
.png){kind=icon}
查看更多内容