Graph Algorithms

Rajeev Motwani, Prabhakar RaghavanCambridge 1995 · DOI · OpenAlex

Abstract

IN this chapter we consider several fundamental optimization problems involving graphs: all-pairs shortest paths, minimum cuts, and minimum spanning trees. In each case, deterministic polynomial time algorithms are known, but the use of randomization allows us to obtain significantly faster solutions for these problems. We show that the problem of computing all-pairs shortest paths is reducible, via a randomized reduction, to the problem of multiplying two integer matrices. We present a fast randomized algorithm for the min-cut problem in undirected graphs, thereby providing evidence that this problem may be easier than the max-flow problem. Finally, we present a linear-time randomized algorithm for the problem of finding minimum spanning trees.
BibTeX
@inproceedings{motwani1995graph,
  author = {Rajeev Motwani and Prabhakar Raghavan},
  title = {{Graph Algorithms}},
  booktitle = {Cambridge},
  year = {1995},
  doi = {10.1017/cbo9780511814075.011},
}

Loading related content...

Figure