Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419464 | Discrete Applied Mathematics | 2012 | 5 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michał Przykucki,