Article ID Journal Published Year Pages File Type
419464 Discrete Applied Mathematics 2012 5 Pages PDF
Abstract

We consider the following on-line decision problem. The vertices of a realization of the random graph G(n,p)G(n,p) are being observed one by one by a selector. At time mm, the selector examines the mmth vertex and knows the graph induced by the mm vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that this vertex has full degree, i.e. it is connected to all other vertices in the graph. An optimal algorithm for such a choice (in other words, optimal stopping time) is given. We show that it is of a threshold type and we find the threshold and its asymptotic estimation.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,