English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In 2005 Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), arestricted but very expressive class of disjunctive temporal problems (DTPs).It was shown that that RDTPs are solvable in deterministic strongly-polynomialtime by reducing them to the Connected Row-Convex (CRC) constraints problem;plus, Kumar devised a randomized algorithm whose expected running time is lessthan that of the deterministic one. Instead, the most general form of DTPsallows for multi-variable disjunctions of many interval constraints and it isNP-complete.  This work offers a deeper comprehension on the tractability of RDTPs, leadingto an elementary deterministic strongly-polynomial time algorithm for them,significantly improving the asymptotic running times of both the deterministicand randomized algorithms of Kumar. The result is obtained by reducing RDTPs tothe 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-3constraint). As a second main contribution, we study the tractability frontierof solving RDTPs by considering Hyper Temporal Networks (\HTNs), a strictgeneralization of \STNs grounded on hypergraphs: on one side, we prove thatsolving temporal problems having only Type-2 constraints and either onlymulti-tail or only multi-head hyperarc constraints lies in both NP and co-NPand it admits deterministic pseudo-polynomial time algorithms; on the otherside, solving problems with Type-3 constraints and either only multi-tail oronly multi-head hyperarc constraints turns strongly NP-complete.

On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier