Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
In this paper, we begin to address the longstanding algorithmic gap between general and reversible Markov chains. We develop directed analogues of several spectral graph-the oretic tools that had previously been available only in the undirected setting, and for which it was not clear that directed v...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Association for Computing Machinery (ACM)
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115991 https://orcid.org/0000-0002-7388-6936 https://orcid.org/0000-0002-4257-4198 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0003-0722-304X |