A recognition algorithm for orders of interval dimension two

Authors

Larry L. Langley, University of the PacificFollow

Document Type

Article

Publication Title

Discrete Applied Mathematics

Department

Mathematics

ISSN

0166-218X

Volume

60

Issue

1--3

DOI

10.1016/0166-218X(94)00056-J

First Page

257

Last Page

266

Publication Date

6-23-1995

Abstract

From a partially ordered set (X, <) one may construct the collection PS(X) consisting of a collection of subsets of X ordered by inclusion. We show that the interval dimension of X equals the dimension of PS(X) and give an O(n³) algorithm to determine whether X has interval dimension ⩽2 and construct an interval realizer of X.