Approximation strategies for generalized binary search in weighted trees

DOI10.4230/LIPICS.ICALP.2017.84zbMATH Open1441.68289arXiv1702.08207MaRDI QIDQ5111415FDOQ5111415

Dariusz Dereniowski, Adrian Kosowski, Przemysław Uznański, Mengchuan Zou

Publication date: 27 May 2020

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

Recommendations

• Improved approximation algorithms for the average-case tree searching problem
• Approximate search strategies for weighted trees
• On the complexity of searching in trees: average-case minimization
• Binary identification problems for weighted trees
• On the complexity of searching in trees and partially ordered structures

zbMATH Keywords

treesapproximation algorithmvertex rankingadaptive algorithmgraph searchbinary search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cited In (10)

• Binary search in graphs revisited
• An efficient noisy binary search in graphs via Median approximation
• Weighted Binary Trees for Concurrent Searching
• An Approximation Algorithm for Binary Searching in Trees
• Edge and pair queries-random graphs and complexity
• Theoretical Analysis of Git Bisect
• Theoretical analysis of git bisect
• On Huang and Wong's algorithm for generalized binary split trees
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth

This page was built for publication: Approximation strategies for generalized binary search in weighted trees

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