An efficient algorithm for stopping on a sink in a directed graph

DOI10.1016/j.orl.2013.02.001zbMath1286.05057OpenAlexW1999027196MaRDI QIDQ2450610

Ewa M. Kubicka, Grzegorz M. Kubicki, Wayne Goddard

Publication date: 14 May 2014

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2013.02.001

zbMATH Keywords

directed graphsecretary problemstopping algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

An optimal algorithm for stopping on the element closest to the center of an interval, Optimal stopping for many connected components in a graph, Maximizing the expected number of components in an online search of a graph, Percolation and best-choice problem for powers of paths, From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path

Cites Work

• Unnamed Item
• Partially ordered secretaries
• Who solved the secretary problem
• Partial-order analogue of the secretary problem: The binary tree case
• The best choice problem for upward directed graphs
• The best-choice problem for partially ordered objects.
• On a universal best choice algorithm for partially ordered sets
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• Dynamic Programming and Decision Theory