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),
IBM Research home page |
James B. Shearer's home page |
- 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,
- C. Brightwell and P. Winkler, "Maximum hitting times for
random walks on graphs", Random structures and Algorithms, 1:263-276,
- 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,
- 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 |
Contact IBM |