My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Finding the hidden path: time bounds for all-pairs shortest paths (1993)

by D.R. Karger, D. Koller, and S. J. Phillips


Abstract: We investigate the all-pairs shortest paths problem in weighted graphs. We present an algorithm-the Hidden Path Algorithm-that finds these paths in time O(m^* n + n^2 LOGn), where m^* is the number of edges participating in shortest paths. Our algorithm is a practical substitute for Dijkstra's algorithm. We argue that m^* is likely to be small in practice, since m^* = O(n log n) with high probability for many probability distributions on edge weights. We also prove an Omega(m n) lower bound on the running time of any path-comparison based algorithm for the all-pairs shortest paths problem. Path-comparison based algorithms form a natural class containing the Hidden Paths Algorithm, as well as the algorithms of Dijkstra and Floyd. Lastly, we consider generalized forms of the shortest paths problem, and show that many of the standard shortest paths algorithms are effective in this more general setting.


Download Information

D.R. Karger, D. Koller, and S. J. Phillips (1993). "Finding the hidden path: time bounds for all-pairs shortest paths." SIAM Journal on Computing, 22(6), 1199-1217. Full version of paper in FOCS '91. pdf ps.gz

Bibtex citation

@article{Karger+al:93,
  author =       "D.R. Karger and D. Koller and S. J. Phillips",
  title =        "Finding the hidden path: time bounds for all-pairs
                 shortest paths",
  journal =      "SIAM Journal on Computing",
  volume =       "22",
  number =       "6",
  pages =        "1199--1217",
  note  =        "Full version of paper in FOCS '91",
  year =         "1993",
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal