BOUNDED DISCRETE REPRESENTATIONS OF INTERVAL ORDERS

A discrete representation of an interval order (A,>) is an interval re presentation for which each interval has integral endpoints. A represe ntation is bounded if each interval is constrained with upper and lowe r bounds on its length. Given a finite interval order and length bound s, we give a polynomial procedure which determines whether or not it h as a bounded discrete representation. The method uses Farkas' lemma to reduce the problem to finding a shortest path or detecting a negative cycle in a corresponding directed graph. Furthermore, we use this dir ected graph to state conditions necessary and sufficient for a represe ntation and examine suborders which block representation in the cases with constant lower bounds of 0 or 1 and constant upper bounds.