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

DOI10.1016/J.DAM.2011.10.023MaRDI QIDQ765377zbMATH OpenOpenAlexFDO

Authors 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

random graphoptimal stoppingvertex with full degree

Mathematics Subject Classification ID

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

Recommendations

• Maximizing the expected number of components in an online search of a graph
• Optimal stopping for many connected components in a graph
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• An efficient algorithm for stopping on a sink in a directed graph
• Gusein-Zade problem for directed path

Cites work

• scientific article; zbMATH DE number 3734865 (Why is no real title available?)
• scientific article; zbMATH DE number 51379 (Why is no real title available?)
• scientific article; zbMATH DE number 67292 (Why is no real title available?)
• scientific article; zbMATH DE number 3322652 (Why is no real title available?)
• Dynamic Programming and Decision Theory
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• Gusein-Zade problem for directed path
• On a best-choice problem by dependent criteria
• On a universal best choice algorithm for partially ordered sets
• On an optimal stopping problem of Gusein-Zade
• Partial-order analogue of the secretary problem: The binary tree case
• Partially ordered secretaries
• Paths in graphs
• The best-choice problem for partially ordered objects.
• Who solved the secretary problem

Cited in

(10)

• Secretary problem with hidden information; searching for a high merit candidate
• An efficient algorithm for stopping on a sink in a directed graph
• Percolation and best-choice problem for powers of paths
• The best choice problem for upward directed graphs
• From directed path to linear order -- the best choice problem for powers of directed path
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• Gusein-Zade problem for directed path
• Optimal stopping for many connected components in a graph
• Maximizing the expected number of components in an online search of a graph
• On randomized stopping points and perfect graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q765377)