| Abstract: | A digraph is an interval digraph if each vertex can be assigned a source interval and a sink interval on the real line such that there is an edge from u to v if and only if the source interval for u intersects the sink interval for v. A digraph is an indifference digraph or unit interval digraph if and only if such a representation can be constructed in which every source and sink interval has unit length. We present a new characterization and an efficient recognition algorithm for indifference digraphs and generalized semiorders. © 1996 John Wiley & Sons, Inc. |
