SATISFIABILITY PROBLEMS ON INTERVALS AND UNIT INTERVALS

For an interval graph with some additional order constraints between p airs of non-intersecting intervals, we give a linear time algorithm to determine if there exists a realization which respects the order cons traints. Previous algorithms for this problem (known also as seriation with side constraints) required quadratic time. This problem contains as subproblems interval graph and interval order recognition. On the other hand, it is a special case of the interval satisfiability proble m, which is concerned with the realizability of a set of intervals alo ng a line, subject to precedence and intersection constraints. We stud y such problems for all possible restrictions on the types of constrai nts, when all intervals must have the same length. We give efficient a lgorithms for several restrictions of the problem, and show the NP-com pleteness of another restriction.