The pyramid path-search equality for triangular query budgets
The pyramid path-search equality for triangular query budgets
Let denote the pyramid graph of height . For a positive integer , let and denote, respectively, the minimum number of rounds needed for path-search and sink-identification when at most queries can be asked in each round. For a positive integer , set
Pyramid path-search conjecture. If for some , then
This extends the fully adaptive equality to larger query budgets, asserting that both search problems have the same optimal round complexity when the budget is triangular. The supplied text does not indicate whether the assertion has been proved or disproved.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Dániel Gerbner and Balázs Keszegh, “Path-search in the pyramid and in other graphs”, arXiv:1104.5098 (2011).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.