Bounded discrete representations of interval orders
Garth Isaak · Discrete Applied Mathematics · 1993
A discrete representation of an interval order (A,≻) is an interval representation for which each interval has integral endpoints. A representation is bounded if each interval is constrained with upper and lower bounds on its length. Given a finite interval order and length bounds, we give a polynomial procedure which determines whether or not it has 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 directed graph to state conditions necessary and sufficient for a representation and examine suborders which block representation in the cases with constant lower bounds of 0 or 1 and constant upper bounds.