Searching in random partially ordered sets

DOI10.1016/J.TCS.2003.06.001MaRDI QIDQ596140zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• scientific article; zbMATH DE number 2086235
• 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

Cites work

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

Cited in

(19)

• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• On the Huffman and alphabetic tree problem with general cost functions
• Binary search in graphs revisited
• Edge ranking and searching in partial orders
• Searching for quicksand ideals in partially ordered sets
• scientific article; zbMATH DE number 2086235 (Why is no real title available?)
• Search in an Ordered Array Having Variable Probe Cost
• On searching a table consistent with division poset
• Partial order multiway search
• 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
• scientific article; zbMATH DE number 2101003 (Why is no real title available?)
• Approximating optimal binary decision trees
• Theoretical analysis of git bisect
• scientific article; zbMATH DE number 2235182 (Why is no real title available?)
• Random search in a bounded area

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)