id: 06015815
dt: j
an: 06015815
au: Przykucki, Michał
ti: Optimal stopping in a search for a vertex with full degree in a random
    graph.
so: Discrete Appl. Math. 160, No. 3, 339-343 (2012).
py: 2012
pu: Elsevier Science B.V. (North-Holland), Amsterdam
la: EN
cc: 
ut: random graph; vertex with full degree; optimal stopping
ci: 
li: doi:10.1016/j.dam.2011.10.023
ab: Summary: We consider the following on-line decision problem. The vertices
    of a realization of the random graph $\cal G(n,p)$ are being observed
    one by one by a selector. At time $m$, the selector examines the mth
    vertex and knows the graph induced by the $m$ 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.
rv: