An efficient noisy binary search in graphs via Median approximation

DOI10.1007/978-3-030-79987-8_19MaRDI QIDQ2115863zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański

Publication date 22 March 2022

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

zbMATH Keywords

graph searchingnoisy searchgraph median

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites work

• scientific article; zbMATH DE number 5764837 (Why is no real title available?)
• scientific article; zbMATH DE number 3547240 (Why is no real title available?)
• scientific article; zbMATH DE number 742943 (Why is no real title available?)
• scientific article; zbMATH DE number 3205803 (Why is no real title available?)
• An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Approximation strategies for generalized binary search in weighted trees
• Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
• Beyond highway dimension: small distance labels using tree skeletons
• Binary search in graphs revisited
• Comparison-based search in the presence of errors
• Computing with Noisy Information
• Coping with errors in binary search procedures
• Deterministic and probabilistic binary search in graphs
• Distance labeling in graphs
• Edge ranking and searching in partial orders
• Highway dimension and provably efficient shortest path algorithms
• Noisy binary search and its applications
• On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
• Optimal Search in Trees
• Optimal edge ranking of trees in linear time
• Optimal node ranking of tree in linear time
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Searching a Tree with Permanently Noisy Advice
• Searching with lies
• Some results on approximate 1-median selection in metric spaces
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• Subcubic equivalences between graph centrality problems, APSP and diameter
• Sublinear time algorithms for metric space problems
• Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
• The centrality index of a graph
• Twenty (simple) questions

Cited in

(2)

• Edge and pair queries-random graphs and complexity
• Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees

This page was built for publication: An efficient noisy binary search in graphs via Median approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115863)