Derandomized Squaring of Graphs
Derandomized Squaring of Graphs
复制标题
图的去随机平方
DOI：
10.1007/11538462_37
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Vadhan
中科院分区：
文献类型：
--
作者：
Eyal Rozenman;S. Vadhan
我们引入图平方的“非随机化”模拟。这个操作增加了图的连通性（通过第二个特征值测量），几乎和对图进行平方一样，但只是通过一个常数因子增加了图的度，而不是对度进行平方。
We introduce a “derandomized” analogue of graph squaring. This operation increases the connectivity of the graph (as measured by the second eigenvalue) almost as well as squaring the graph does, yet only increases the degree of the graph by a constant factor, instead of squaring the degree.
One application of this product is an alternative proof of Reingold's recent breakthrough result that S-T Connectivity in Undirected Graphs can be solved in deterministic logspace.