On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier

DOI10.4230/LIPIcs.TIME.2018.10zbMath1487.68211arXiv1805.02183OpenAlexW2963999652MaRDI QIDQ5079776

Carlo Comin, Romeo Rizzi

Publication date: 28 May 2022

Full work available at URL: https://arxiv.org/abs/1805.02183

zbMATH Keywords

consistency checking2-SAThyper-temporal networkssimple temporal networksrestricted disjuctive temporal problemssingle-source shortest-paths

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• A note on two problems in connexion with graphs
• Temporal constraint networks
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Constraint satisfaction over connected row-convex constraints
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• On a routing problem

This page was built for publication: On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier