Abstract: Suppose distinct real numbers are assigned by a storage function to the elements of a finite poset P in an order preserving manner. The problem of determining the fewest number of comparisons needed to locate a given number α is studied for the case when dim P ≤ 2. We develop an improved algorithm for this search problem, by searching the values stored at the central elements of appropriately chosen subposets. We also present an algorithm which finds the central element of 2-dimensional posets in polynomial time. We conclude by an interesting consequence of these results, by showing that every finite planar distributive lattice L has a prime ideal containing at least 14 but at most 34 of the elements of L.
Publication Year: 1987
Publication Date: 1987-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 10
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot