@conference {642398,
	title = {S-T connectivity on digraphs with a known stationary distribution},
	booktitle = {ACM Transactions on Algorithms},
	volume = {7},
	year = {2011},
	publisher = {ACM},
	organization = {ACM},
	edition = {3},
	abstract = {
	Version history: Preliminary versions in CCC {\textquoteright}07 and on ECCC (TR07-030).



	We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices\&nbsp;\(s\)\&nbsp;and\&nbsp;\(t\)\&nbsp;have nonnegligible probability mass and (ii) the random walk which starts at the source vertex\&nbsp;\(s\)\&nbsp;has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for S-T Connectivity on undirected graphs [Reingold, 2008]. 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).



	\&nbsp;

},
	url = {https://dl.acm.org/citation.cfm?id=1978785},
	author = {Kai-Min Chung and Omer Reingold and Salil Vadhan}
}
