Optimization Algorithms on Random Graphs
Douglas G. Kelly, Dominic J. A. Welsh · NCSU Libraries Repository (North Carolina State University Libraries) · 1982
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=1-p. On such a graph we consider two different random walks starting with vertex n, moving at each step from a vertex to a lower-numbered neighbor, and stopping when they reach either vertex 0 or a sink, a vertex with no lower-numbered 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.