Searching in random partially ordered sets

DOI10.1016/j.tcs.2003.06.001zbMath1068.68050OpenAlexW2697349394MaRDI QIDQ596140

Yoshiharu Kohayakawa, Jair Donadelli, Eduardo Sany Laber, Renato Carmo

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2003.06.001

zbMATH Keywords

SearchingRandom partial ordersSearch trees

Mathematics Subject Classification ID

Partial orders, general (06A06) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Approximation algorithms (68W25)

Related Items (9)

On searching a table consistent with division poset ⋮ Theoretical analysis of git bisect ⋮ Approximating optimal binary decision trees ⋮ An approximation algorithm for binary searching in trees ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Binary search in graphs revisited ⋮ On the Huffman and alphabetic tree problem with general cost functions ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Every poset has a central element
• Constructing optimal binary decision trees is NP-complete
• Linear extensions of a random partial order
• On tail distribution of interpost distance
• The average number of linear extensions of a partial order
• Counting Partial Orders with a Fixed Number of Comparable Pairs
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Searching ordered structures
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Optimal Search in Trees
• The Structure of Random Graph Orders
• Decision Trees for Geometric Models
• Minimum average cost testing for partially ordered components
• Phase transitions in the evolution of partial orders

This page was built for publication: Searching in random partially ordered sets