Binary Search in Graphs Revisited

DOI10.4230/LIPIcs.MFCS.2017.20zbMath1441.68028arXiv1702.08899OpenAlexW2897701371MaRDI QIDQ5111234

Argyrios Deligkas, George B. Mertzios, Paul G. Spirakis

Publication date: 26 May 2020

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

zbMATH Keywords

graphlower boundprobabilistic algorithmbinary searchapproximate query

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of searching in trees and partially ordered structures
• Edge ranking and searching in partial orders
• Optimal node ranking of trees
• Edge ranking of graphs is hard
• The binary identification problem for weighted trees
• Optimal node ranking of tree in linear time
• Some Recent Results in Heuristic Search Theory
• Sorting and Selection in Posets
• Searching ordered structures
• Optimal Search in Trees
• Computing with Noisy Information
• Searching a Tree with Permanently Noisy Advice
• Deterministic and probabilistic binary search in graphs
• Optimal edge ranking of trees in linear time
• Searching games with errors -- fifty years of coping with liars

This page was built for publication: Binary Search in Graphs Revisited