Searching in random partially ordered sets

DOI10.1016/J.TCS.2003.06.001zbMATH Open1068.68050OpenAlexW2697349394MaRDI QIDQ596140FDOQ596140

Jair Donadelli, Eduardo S. Laber, Renato Carmo, Yoshiharu Kohayakawa

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

Random partial ordersSearch treesSearching

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (16)

• On the Huffman and alphabetic tree problem with general cost functions
• Binary search in graphs revisited
• Title not available (Why is that?)
• Search in an Ordered Array Having Variable Probe Cost
• On searching a table consistent with division poset
• Partial fillup and search time in LC tries
• Pictures from Mongolia. Extracting the top elements from a partially ordered set
• An approximation algorithm for binary searching in trees
• On the complexity of searching in trees and partially ordered structures
• Theoretical Analysis of Git Bisect
• Title not available (Why is that?)
• Approximating optimal binary decision trees
• Theoretical analysis of git bisect
• Random search in a bounded area
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth

   Recommendations

• Title not available (Why is that?) 👍 👎
• Edge ranking and searching in partial orders 👍 👎
• Optimal Search in Trees 👍 👎
• Searching ordered structures 👍 👎
• A lower bound for the complexity of information networks for one partial order relation 👍 👎

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

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