Optimal stopping in a search for a vertex with full degree in a random graph

DOI10.1016/j.dam.2011.10.023zbMath1237.05191OpenAlexW2153656244MaRDI QIDQ765377

Michał Przykucki

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.023

zbMATH Keywords

optimal stoppingrandom graphvertex with full degree

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07)

Related Items (4)

The best choice problem for upward directed graphs ⋮ Percolation and best-choice problem for powers of paths ⋮ From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path ⋮ Secretary problem with hidden information; searching for a high merit candidate

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partially ordered secretaries
• On an optimal stopping problem of Gusein-Zade
• Who solved the secretary problem
• Partial-order analogue of the secretary problem: The binary tree case
• Gusein-Zade problem for directed path
• The best-choice problem for partially ordered objects.
• On a universal best choice algorithm for partially ordered sets
• On a best-choice problem by dependent criteria
• Paths in graphs
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• Dynamic Programming and Decision Theory

This page was built for publication: Optimal stopping in a search for a vertex with full degree in a random graph