An efficient noisy binary search in graphs via Median approximation
From MaRDI portal
Publication:2115863
DOI10.1007/978-3-030-79987-8_19OpenAlexW3183688096MaRDI QIDQ2115863
Aleksander Łukasiewicz, Dariusz Dereniowski, Przemysław Uznański
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2005.00144
Related Items (2)
Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Edge and pair queries-random graphs and complexity
Cites Work
- Some results on approximate 1-median selection in metric spaces
- Edge ranking and searching in partial orders
- Coping with errors in binary search procedures
- Binary search in graphs revisited
- Optimal node ranking of tree in linear time
- Searching with lies
- The centrality index of a graph
- Sublinear time algorithms for metric space problems
- Highway Dimension and Provably Efficient Shortest Path Algorithms
- State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
- On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
- Optimal Search in Trees
- Computing with Noisy Information
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Distance labeling in graphs
- Twenty (simple) questions
- Searching a Tree with Permanently Noisy Advice
- Comparison-based search in the presence of errors
- Deterministic and probabilistic binary search in graphs
- Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
- An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- Optimal edge ranking of trees in linear time
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: An efficient noisy binary search in graphs via Median approximation
