Catalog
- Results include
-
Random sampling in graph optimization problems
February 1995.The representative random sample is a central concept of statistics. It is often possible to gather a great deal of information about a large population by examining a small sample randomly drawn from it. This approach has obvious advantages in reducing the investigator's work, both in gathering and in analyzing the data. We apply the concept of a representative sample to combinatorial optimization. Our focus is optimization problems on undirected graphs. Highlights of our results include: The first (randomized) linear time minimum spanning tree algorithm; A (randomized) minimum cut algorithm with running time roughly O(n[superscript]2) as compared to previous roughly O(n[superscript]3) time bounds, as well as the first algorithm for finding all approximately minimal cuts and multiway cuts; An efficient parallelization of the minimum cut algorithm, providing the first parallel (RNC) algorithm for minimum cuts; A derandomization finding minimum cut in NC; Provably accurate approximations to network reliability; Very fast approximation algorithms for minimum cuts, s-t minimum cuts, and maximum flows; Significantly improved polynomial-time approximation bounds for network design problems; For coloring 3-colorable graphs, improvements in the approximation bounds from O(n[superscript]{3/8}) to O(n[superscript]{1/4}); An analysis of random sampling in Matroids.
Guides
Library website
Exhibits
EarthWorks
More search tools
Tools to help you discover resources at Stanford and beyond.