Optimal stopping for many connected components in a graph

DOI10.1002/rsa.21000zbMath1522.05469arXiv2001.07870OpenAlexW3130812290MaRDI QIDQ6074658

Michał Lasoń

Publication date: 12 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.07870

zbMATH Keywords

optimal stopping\(k\)-treeconnected component

Mathematics Subject Classification ID

Trees (05C05) Stopping times; optimal stopping problems; gambling theory (60G40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Maximizing the expected number of components in an online search of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Partially ordered secretaries
• Who solved the secretary problem
• Partial-order analogue of the secretary problem: The binary tree case
• Sum the odds to one and stop
• The best choice problem for upward directed graphs
• The best-choice problem for partially ordered objects.
• Maximizing the expected number of components in an online search of a graph
• An efficient algorithm for stopping on a sink in a directed graph
• On a universal best choice algorithm for partially ordered sets
• Poisson approximation for large deviations
• Percolation and best-choice problem for powers of paths
• 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
• Dynamic Programming and Decision Theory

This page was built for publication: Optimal stopping for many connected components in a graph