Searching a Tree with Permanently Noisy Advice

DOI10.4230/LIPIcs.ESA.2018.54OpenAlexW2963173231MaRDI QIDQ5009618

Lucas Boczkowski, Yoav Rodeh, Amos Korman

Publication date: 4 August 2021

Full work available at URL: https://hal.archives-ouvertes.fr/hal-01958133

zbMATH Keywords

data structuresaverage case analysisgraph search

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (9)

Pebble guided optimal treasure hunt in anonymous graphs ⋮ The faulty Satnav (GPS) problem: search for home in networks with unreliable directions ⋮ Binary search in graphs revisited ⋮ Unnamed Item ⋮ Slowdown for the geodesic-biased random walk ⋮ Search for an immobile hider on a stochastic network ⋮ Binary Search in Graphs Revisited ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ Pebble guided near optimal treasure hunt in anonymous graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Memoryless search algorithms in a network with faulty advice
• Searching with mobile agents in networks with liars.
• Optimal strategies against a liar
• Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles
• Selected Topics in Random Walks in Random Environment
• Optimal Resilient Dynamic Dictionaries
• Sorting and searching in the presence of memory faults (without redundancy)
• Optimal Search in Trees
• Computing with Noisy Information
• Locating a target with an agent guided by unreliable local advice
• Comparison-based search in the presence of errors
• Deterministic and probabilistic binary search in graphs
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Searching a Tree with Permanently Noisy Advice