  In 2005 Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a
restricted but very expressive class of disjunctive temporal problems (DTPs).
It was shown that that RDTPs are solvable in deterministic strongly-polynomial
time by reducing them to the Connected Row-Convex (CRC) constraints problem;
plus, Kumar devised a randomized algorithm whose expected running time is less
than that of the deterministic one. Instead, the most general form of DTPs
allows for multi-variable disjunctions of many interval constraints and it is
NP-complete.
  This work offers a deeper comprehension on the tractability of RDTPs, leading
to an elementary deterministic strongly-polynomial time algorithm for them,
significantly improving the asymptotic running times of both the deterministic
and randomized algorithms of Kumar. The result is obtained by reducing RDTPs to
the Single-Source Shortest-Paths (SSSP) and the 2-SAT problem (jointly),
instead of reducing to CRCs. In passing, we obtain a faster (quadratic-time)
algorithm for RDTPs having only Type-1 and Type-2 constraints (and no Type-3
constraint). As a second main contribution, we study the tractability frontier
of solving RDTPs by considering Hyper Temporal Networks (\HTNs), a strict
generalization of \STNs grounded on hypergraphs: on one side, we prove that
solving temporal problems having only Type-2 constraints and either only
multi-tail or only multi-head hyperarc constraints lies in both NP and co-NP
and it admits deterministic pseudo-polynomial time algorithms; on the other
side, solving problems with Type-3 constraints and either only multi-tail or
only multi-head hyperarc constraints turns strongly NP-complete.
