{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:12:49Z","timestamp":1770894769174,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications.\nIt is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allen's interval algebra can be solved in single-exponential time, by giving a 2^{O(nloglog(n))} algorithm for the special case of unit-length intervals.<\/jats:p>","DOI":"10.24963\/kr.2020\/29","type":"proceedings-article","created":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T04:39:16Z","timestamp":1597898356000},"page":"284-293","source":"Crossref","is-referenced-by-count":0,"title":["Fine-Grained Complexity of Temporal Problems"],"prefix":"10.24963","author":[{"given":"Konrad K.","family":"Dabrowski","sequence":"first","affiliation":[{"name":"Durham University"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University"}]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[{"name":"University of Sheffield"}]},{"given":"George","family":"Osipov","sequence":"additional","affiliation":[{"name":"Link\u00f6ping University"}]}],"member":"10584","event":{"name":"17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}","theme":"Artificial Intelligence","location":"Rhodes, Greece","acronym":"KR-2020","number":"17","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Association for Logic Programming","Center for Perspicuous Computing","European Association for Artificial Intelligence","Ontopic - The Virtual Knowledge Graph Company"],"start":{"date-parts":[[2020,9,12]]},"end":{"date-parts":[[2020,9,18]]}},"container-title":["Proceedings of the Seventeenth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2020,11,5]],"date-time":"2020-11-05T21:18:35Z","timestamp":1604611115000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2020\/29"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2020\/29","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}