ALGORITHMS FOR INTERVAL CATCH DIGRAPHS

A family ((S(v), T(v))\v is-an-element-of V) of ordered pairs of inter vals of the real line, each S, containing its corresponding T(v), is c alled a nest representation. A directed graph D = (V, A) is an interva l nest digraph if there is some nest representation with index set V s uch that xy is-an-element-of A if and only if S(x) and T(y) not-equal theta. Interval catch digraphs allow nest representations where each s et T(v) contains just one element. In this paper we show that the foll owing problems can be solved efficiently for interval catch digraphs: (1) The RECOGNITION problem, (2) CLIQUE, CHROMATIC NUMBER, INDEPENDENT SET, PARTITION INTO CLIQUES and (3) KERNEL-finding an independent and absorbing vertex set, and SOLUTION-finding an independent and dominat ing vertex set. The problems of (2) and (3) can be solved even for int erval nest digraphs if a nest representation is known.