Derandomized Squaring of Graphs | Zendy

Eyal Rozenman | Zendy; Salil Vadhan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Derandomized Squaring of Graphs

Author(s) -

Eyal Rozenman,

Salil Vadhan

Publication year - 2005

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-28239-4

DOI - 10.1007/11538462_37

Subject(s) - graph , degree (music) , undirected graph , mathematics , combinatorics , eigenvalues and eigenvectors , discrete mathematics , computer science , physics , quantum mechanics , acoustics

We introduce a "derandomized" analogue of graph squaring. This op- eration 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 re- cent breakthrough result that S-T Connectivity in Undirected Graphs can be solved in deterministic logspace.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research