From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path

DOI10.1137/130950689zbMath1350.05049arXiv1308.2644OpenAlexW2010833765MaRDI QIDQ5251623

Małgorzata Sulkowska, Andrzej Grzesik, Michał Morayne

Publication date: 20 May 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

directed graphbest choicesecretary problemgraph power

Mathematics Subject Classification ID

Paths and cycles (05C38) Stopping times; optimal stopping problems; gambling theory (60G40) Directed graphs (digraphs), tournaments (05C20)

Related Items (3)

Optimal stopping for many connected components in a graph ⋮ Percolation and best-choice problem for powers of paths ⋮ Counting embeddings of rooted trees into families of rooted trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partially ordered secretaries
• Optimal stopping in a search for a vertex with full degree in a random graph
• Who solved the secretary problem
• Partial-order analogue of the secretary problem: The binary tree case
• The best choice problem for upward directed graphs
• Gusein-Zade problem for directed path
• The best-choice problem for partially ordered objects.
• The best choice problem for a union of two linear orders with common maximum
• An efficient algorithm for stopping on a sink in a directed graph
• The secretary problem on an unknown poset
• How to Choose the Best Twins
• On a universal best choice algorithm for partially ordered sets
• An Upper Bound for Spherical Caps
• Graph-Theoretic Generalization of the Secretary Problem: The Directed Path Case
• Dynamic Programming and Decision Theory
• The best choice problem for posets; colored complete binary trees

This page was built for publication: From Directed Path to Linear Order---The Best Choice Problem for Powers of Directed Path