An efficient noisy binary search in graphs via Median approximation
type: Item
instance of: scholarly article
title: An efficient noisy binary search in graphs via Median approximation
DOI: 10.1007/978-3-030-79987-8_19
author: Dariusz Dereniowski
author: Aleksander Łukasiewicz
author: Przemysław Uznański
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2005.00144
Mathematics Subject Classification ID: 68Rxx
Mathematics Subject Classification ID: 68Wxx
zbMATH DE Number: 7495028
zbMATH Keywords: graph median
zbMATH Keywords: graph searching
zbMATH Keywords: noisy search
MaRDI profile type: Publication
OpenAlex ID: W3183688096
cites work: Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
cites work: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
cites work: Highway Dimension and Provably Efficient Shortest Path Algorithms
cites work: Searching with lies
cites work: Optimal Search in Trees
cites work: Searching a Tree with Permanently Noisy Advice
cites work: Comparison-based search in the presence of errors
cites work: Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
cites work: An Efficient Approximate Algorithm for the 1-Median Problem in Metric Spaces
cites work: Some results on approximate 1-median selection in metric spaces
cites work: Q5351928
cites work: Twenty (simple) questions
cites work: Binary search in graphs revisited
cites work: Edge ranking and searching in partial orders
cites work: Q5111415
cites work: Q4763384
cites work: Deterministic and probabilistic binary search in graphs
cites work: Computing with Noisy Information
cites work: Distance labeling in graphs
cites work: Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
cites work: Sublinear time algorithms for metric space problems
cites work: Q2934677
cites work: Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
cites work: Optimal edge ranking of trees in linear time
cites work: Q3579429
cites work: On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
cites work: Coping with errors in binary search procedures
cites work: Q5331663
cites work: The centrality index of a graph
cites work: Optimal node ranking of tree in linear time
cites work: State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
cites work: Q4121861
description: scientific article; zbMATH DE number 7495028