Binary search in graphs revisited

DOI10.1007/s00453-018-0501-yzbMath1422.68058OpenAlexW2594084810MaRDI QIDQ1741841

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

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0501-y

zbMATH Keywords

graphlower boundprobabilistic algorithmbinary searchapproximate query

Mathematics Subject Classification ID

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

Related Items (1)

An efficient noisy binary search in graphs via Median approximation

Cites Work

• Searching in random partially ordered sets
• 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
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Binary search in graphs revisited