On the tractability of restricted disjunctive temporal problems
T. K. Satish Kumar · 2005
In this paper, we provide a polynomial-time deterministic al-gorithm, and an even simpler randomized algorithm, for solv-ing a restricted (but very expressive) class of disjunctive tem-poral problems (DTPs). The general form of a DTP is as fol-lows. We are given a set of events X = {X0,X1...XN} (X0 is the “beginning of the world ” node and is set to 0 by convention), and a set of constraints C. A constraint ci ∈ C is a disjunction of the form s(i,1) ∨ s(i,2)... s(i,Ti). Here, s(i,j) (1 ≤ j ≤ Ti) is a simple temporal con-straint of the form L(i,j) ≤ Xb(i,j) − Xa(i,j) ≤ U(i,j) for 0 ≤ a(i,j), b(i,j) ≤ N. We will first provide a pseudo-polynomial-time randomized algorithm for solving the fol-lowing restricted class of DTPs (which we will refer to as RDTPs (restricted DTPs)): Any ci ∈ C is of one of the fol-