Partial order multiway search

DOI10.1145/3626956MaRDI QIDQ6535268zbMATH OpenFDO

Authors Shangqi Lu, Wim Martens, Matthias Niewerth, Yufei Tao

Publication date 29 November 2023

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3626956

zbMATH Keywords

data structuresgraph algorithmslower boundspartial order

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Deterministic and probabilistic binary search in graphs
• Searching in random partially ordered sets
• Edge ranking and searching in partial orders
• Binary search in graphs revisited
• Binary search in graphs revisited

Cites work

• A fast planar partition algorithm. I
• A framework for searching in graphs in the presence of errors
• About groups of straight lines
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• An approximation algorithm for binary searching in trees
• Approximating Decision Trees with Multiway Branches
• Approximating optimal binary decision trees
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• Decision trees for entity identification, approximation algorithms and hardness results
• Decision Trees for Geometric Models
• Deterministic and probabilistic binary search in graphs
• Dynamic Planar Point Location in External Memory.
• Edge ranking and searching in partial orders
• Edge ranking of weighted trees
• scientific article; zbMATH DE number 2185610 (Why is no real title available?)
• scientific article; zbMATH DE number 2086235 (Why is no real title available?)
• scientific article; zbMATH DE number 5764837 (Why is no real title available?)
• scientific article; zbMATH DE number 1303585 (Why is no real title available?)
• scientific article; zbMATH DE number 5033869 (Why is no real title available?)
• scientific article; zbMATH DE number 6472652 (Why is no real title available?)
• I/O-efficient point location using persistent B-trees
• Improved approximation algorithms for the average-case tree searching problem
• Introduction to algorithms
• On an edge ranking problem of trees and graphs
• On greedy algorithms for decision trees
• On the complexity of searching in trees and partially ordered structures
• On the complexity of searching in trees: average-case minimization
• On the tree search problem with non-uniform costs
• Optimal edge ranking of trees in polynomial time
• Optimal Search in Trees
• Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
• The binary identification problem for weighted trees
• Topology B-trees and their applications

Cited in

(2)

• Linearizing partial search orders
• Generalized sorting with predictions revisited

This page was built for publication: Partial order multiway search

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