loading...
S-T Connectivity on Digraphs with a Known Stationary Distribution
San Diego, California June 13-March 16
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2007.30Twenty-Second Annual IEEE Conference ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Kai-Min Chung, Omer Reingold, Salil Vadhan, "S-T Connectivity on Digraphs with a Known Stationary Distribution," Computational Complexity, Annual IEEE Conference on, pp. 236-249, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2007.30,
author = {Kai-Min Chung and Omer Reingold and Salil Vadhan},
title = {S-T Connectivity on Digraphs with a Known Stationary Distribution},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2007},
issn = {1093-0159},
pages = {236-249},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.30},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - S-T Connectivity on Digraphs with a Known Stationary Distribution
SN - 1093-0159
SP236
EP249
A1 - Kai-Min Chung,
A1 - Omer Reingold,
A1 - Salil Vadhan,
PY - 2007
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Kai-Min Chung, Harvard University, USA
Omer Reingold, Weizmann Institute of Science, Israel
Salil Vadhan, Harvard University, USA
We present a deterministic logspace algorithm for solving S-T CONNECTIVITY on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex s has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T CONNECTIVITY on undirected graphs [15]. It identifies knowledge of the stationary distribution as the gap between the S-T CONNECTIVITY problems we know how to solve in logspace (L) and those that capture all of randomized logspace (RL).
Citation:
Kai-Min Chung, Omer Reingold, Salil Vadhan, "S-T Connectivity on Digraphs with a Known Stationary Distribution," ccc, pp.236-249, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.