
Accession Number : ADA115804
Title : Optimization Algorithms on Random Graphs,
Corporate Author : NORTH CAROLINA UNIV AT CHAPEL HILL INST OF STATISTICS
Personal Author(s) : Kelly,D G ; Welsh,D J A
PDF Url : ADA115804
Report Date : Apr 1982
Pagination or Media Count : 13
Abstract : We consider random graphs on vertices 0,1,2,...,n in which each edge, independent of the others, is present with probability p and absent with probability q=1p. On such a graph we consider two different random walks starting with vertex n, moving at each step from a vertex to a lowernumbered neighbor, and stopping when they reach either vertex 0 or a sink, a vertex with no lowernumbered neighbor. These walks are simplified attempts to reproduce probabilistically the behavior of the simplex algorithm on linear programs. We derive some simple asymptotic results on the distribution of the number of sinks in a random graph, and also on the distributions of the numbers of steps needed by each of the two random walks.
Descriptors : *Algorithms, *Points(Mathematics), *Simplex method, Optimization, Graphs, Probability distribution functions, Asymptotic series, Random variables, Problem solving
Subject Categories : Statistics and Probability
Distribution Statement : APPROVED FOR PUBLIC RELEASE