Graph Algorithms
Lists
Only you see this
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...