This web page lists the references in my paper:

"Random Walks on Regular and Irregular Graphs", with D. Coppersmith and U. Feige, Siam J. Discrete Math., 9(1996), p. 301-308.

- D. J. Aldous, "Reversible Markov chains and random walks on graphs", Draft of first six chapters of book, January 26, 1993.
- R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz and C. Rackoff, "Random walks, universal traversal sequences, and the complexity of maze problems", in 20th annual Symposium on Foundations of Computer Science, pages 218-223, San Juan, Puerto Rico, October 1979.
- S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, "Proof Verification and Hardness of Approximation Problems", in Proc. of 33rd Annual Symposium on Foundations of Computer Science, 14-23, 1992.
- B. Bollobas, Graph Theory: An Introductory Course, Springer, 1979.
- C. Brightwell and P. Winkler, "Maximum hitting times for random walks on graphs", Random structures and Algorithms, 1:263-276, 1990.
- A. Chandra, P. Raghavan, W. Ruzzo, R. Smolensky and P. Tiwari, "The electrical resistance of a graph captures its commute and cover times", in Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 574-586, Seattle, WA, May 1989.
- N. Christofides, "Worse-case analysis of a new heuristic for the travelling salesman problem", Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA.
- D. Coppersmith, P. Tetali and P. Winkler, "Collisions among random walks on a graph", SIAM J. on Discrete Math., 6(3):363-374, August 1993.
- P. G. Doyle and J. L. Snell, "Random Walks and Electrical Networks", The Mathematical Association of America, 1984.
- U. Feige, "A Tight Upper Bound on the Cover Time for Random Walks on Graphs", Random Structures and Algorithms, 6(1):51-54, 1995.
- U. Feige, "A randomized time-space tradeoff of O(mR) for USTCON", Proc. of 34th Annual Symposium on Foundations of Computer Science, pp. 238-246, 1993.
- R. Foster, "The average impedance of an electrical network" Contributions to applied mechanics (Reissner anniversary volume), Ann Arbor, pp. 333-340, Edwards Brothers Inc., 1949.
- M. Garey and D. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, 1979.
- J. D. Kahn, N. Linial, N. Nisan and M. E. Saks, "On the cover time of random walks on graphs", Journal of Theoretical Probability, 2(1):121-128, January 1989.
- P. C. Matthews, "Covering Problems for Brownian Motion on Spheres", Ann. Probab., 16:189-199, 1988.
- P. Tetali, "Random walks and the effective resistance of networks", Journal of Theoretical Probability, 4:101-109, 1991.

[ IBM home page | Order | Search | Contact IBM | Legal ]