{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:44:56Z","timestamp":1766065496017,"version":"3.41.2"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[1998,6]]},"DOI":"10.1023\/a:1009717525330","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T17:50:41Z","timestamp":1040579441000},"page":"129-149","source":"Crossref","is-referenced-by-count":71,"title":["Temporal Constraints: A Survey"],"prefix":"10.1007","volume":"3","author":[{"given":"Eddie","family":"Schwalb","sequence":"first","affiliation":[]},{"given":"Llu\u00eds","family":"Vila","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"163064_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. Allen","year":"1983","unstructured":"J. Allen. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM 26: 832\u2013843.","journal-title":"Communications of the ACM"},{"key":"163064_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"K. R. Baker","year":"1972","unstructured":"K. R. Baker, P. C. Fishburn, & F. S. Roberts. (1972). Partial orders of dimension 2. Networks 2:11\u201328.","journal-title":"Networks"},{"key":"163064_CR3","unstructured":"A. Belfer & M. Golumbic. (1981). The role of combinatorical sructures in temporal reasoning. Technical report, IBM research report."},{"key":"163064_CR4","doi-asserted-by":"crossref","unstructured":"A. Belfer & M. Golumbic. (1990). A combinatorical approach to temporal reasoning. In Proc. Information Technology IEEE, pages 774\u2013780.","DOI":"10.1109\/JCIT.1990.128360"},{"key":"163064_CR5","unstructured":"C. Bessiere, A. Isli, & G. Ligozat. (1996). Global consistency in interval algebra networks: Tractable subclasses. In Proc. ECAI'96, pages 3\u20137."},{"key":"163064_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth & G. S. Leuker. (1976). Testing for the consecutive ones property, interval graphs, and planarity using pq-tree algorithms. J. Comput. Sys. Sci. 13: 335\u2013379.","journal-title":"J. Comput. Sys. Sci"},{"key":"163064_CR7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A. Bouchet","year":"1987","unstructured":"A. Bouchet. (1987). Reducing prime graphs and recognizing circle graphs. Combinatorics 7: 243\u2013254.","journal-title":"Combinatorics"},{"key":"163064_CR8","unstructured":"P. Cheesman & B. Kanefsky. (1991). Where the really hard problems are. In Proc. IJCAI'91, pages 163\u2013169."},{"key":"163064_CR9","unstructured":"T. Cormen, C. Leiserson, & R. Rivest. (1990). Introduction to Algorithms. McGraw Hill."},{"key":"163064_CR10","unstructured":"R. Dechter. (1992). Encyclopedia of Artificial Intelligence, chapter Constraint Networks. John Wiley & Sons Inc., 2nd edition."},{"key":"163064_CR11","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0004-3702(91)90006-6","volume":"49","author":"R. Dechter","year":"1991","unstructured":"R. Dechter, I. Meiri, & J. Pearl. (1991). Temporal constraint networks. Artificial Intelligence 49: 61\u201395.","journal-title":"Artificial Intelligence"},{"key":"163064_CR12","unstructured":"T. Drakengren & P. Jonsson. (1996). Maximal tractable subclasse of Allen's interval algebra: Preliminary report. In Proc. AAAI'96, pages 389\u2013394."},{"key":"163064_CR13","unstructured":"T. Drakengren & P. Jonsson. (1997). Towards a complete classification of tractability in Allen's algebra. In Proc. IJCAI'97, pages 389\u2013394."},{"key":"163064_CR14","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B. Dushnik","year":"1941","unstructured":"B. Dushnik & E. W. Miller. (1941). Partially ordered sets. Amer. J. Math 63: 600\u2013610.","journal-title":"Amer. J. Math"},{"key":"163064_CR15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0004-3702(92)90090-K","volume":"54","author":"C. Freksa","year":"1992","unstructured":"C. Freksa. (1992). Temporal reasoning based on semi-intervals. Artificial Intelligence 54: 199\u2013227.","journal-title":"Artificial Intelligence"},{"key":"163064_CR16","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson & O. A. Gross. (1965). Incidence matrices and interval graphs. Pacific J. Math. 15: 835\u2013855.","journal-title":"Pacific J. Math"},{"key":"163064_CR17","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/65950.65951","volume":"36","author":"C. P. Gabor","year":"1989","unstructured":"C. P. Gabor, K. J. Supowit, & W. L. Hsu. (1989). Recognizing circle graphs in polynomial time. J. ACM 36: 435\u2013473.","journal-title":"J. ACM"},{"key":"163064_CR18","unstructured":"A. Gerevini & M. Cristani. (1997). On finding a solution in temporal constraint satisfaction problems. In Proc. IJCAI'97, pages 1460\u20131465."},{"key":"163064_CR19","unstructured":"A. Gerevini & Lenhart Schubert. (1993). Efficient temporal reasoning through timegraphs. In Proc. IJCAI'93, pages 648\u2013654."},{"key":"163064_CR20","unstructured":"A. Gerevini & L. Schubert. (1994). On computing the minimal labels in time point algebra networks. Technical Report 9408\u201310, Insituto per la Ricerca Scientifica e Tecnologica."},{"issue":"3","key":"163064_CR21","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0004-3702(94)00016-T","volume":"74","author":"A. Gerevini","year":"1995","unstructured":"A. Gerevini & L. Schubert. (1995). Efficient algorithms for qualitative reasoning about time. Artificial Intelligence 74(3): 207\u2013248.","journal-title":"Artificial Intelligence"},{"key":"163064_CR22","unstructured":"M. Ghallab & A. M. Alaoui. (1989). Managing efficiently temporal relations through indexed spanning trees. In Proc. IJCAI'89, pages 1297\u20131303."},{"key":"163064_CR23","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"P. C. Gilmore & A. J. Hoffman. (1964). A characterization of comparability graphs and interval graphs. Canadian J. Math 16: 539\u2013548.","journal-title":"Canadian J. Math"},{"key":"163064_CR24","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1111\/j.1749-6632.1989.tb22452.x","volume":"555","author":"M. Golumbic","year":"1989","unstructured":"M. Golumbic & E. Scheinerman. (1989). Containment graphs, posets and related classes of graphs. Ann. N. Y. Acad. Sci 555: 192\u2013204.","journal-title":"Ann. N. Y. Acad. Sci"},{"key":"163064_CR25","series-title":"Technical Report","volume-title":"Algorithms and complexity for reasoning about time","author":"M. Golumbic","year":"1992","unstructured":"M. Golumbic & R. Shamir. (1992). Algorithms and complexity for reasoning about time. Technical Report 22\u201391, Rutgers, New Jersey."},{"key":"163064_CR26","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","volume":"14","author":"R. Haralick","year":"1980","unstructured":"R. Haralick & G. Elliot. (1980). Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence 14: 263\u2013313.","journal-title":"Artificial Intelligence"},{"key":"163064_CR27","unstructured":"P. Jonsson, T. Drakengren, & C. Backstrom. (1996). Tractable subclasses of the poinot-interval algebra: A complete classification. In Proc. KR'96, pages 352\u2013363. AAAI Press\/The MIT Press."},{"key":"163064_CR28","unstructured":"H. Kautz & P. Ladkin. (1991). Integrating metric and qualitative temporal reasoning. In Proc. AAAI'91, pages 241\u2013246."},{"key":"163064_CR29","unstructured":"J. Koomen. (1987). The TIMELOGIC temporal reasoning system. Technical report 231, Univ. of Rochester, Computer Science Dept. (revised March 1989)."},{"key":"163064_CR30","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"N. Korte & R. H. M\u00f6hring. (1989). An incremental linear time algorithm for recognizing interval graphs. SIAM J. Comput. 18: 68\u201381.","journal-title":"SIAM J. Comput"},{"key":"163064_CR31","unstructured":"M. Koubarakis. (1992). Dense time and temporal constraints with 6D. In Proc. KR'92, pages 24\u201335."},{"key":"163064_CR32","doi-asserted-by":"crossref","unstructured":"M. Koubarakis. (1995). From local to global consistency in temporal constraint networks. In Proc. CP'95.","DOI":"10.1007\/3-540-60299-2_4"},{"key":"163064_CR33","doi-asserted-by":"crossref","unstructured":"M. Koubarakis. (1996). Tractable disjunctions of linear constraints. In Proc. CP'96, pages 297\u2013397.","DOI":"10.1007\/3-540-61551-2_82"},{"key":"163064_CR34","unstructured":"P. Ladkin & R. D. Maddux. (1988). The algebra of constraint satisfaction problems and temporal reasoning. Technical report, Krestel Institute."},{"key":"163064_CR35","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0004-3702(92)90106-8","volume":"57","author":"P. Ladkin","year":"1992","unstructured":"P. Ladkin & A. Reinefeld. (1992). Effective solution of qualitative interval constraint problems. Artificial Intelligence 57: 105\u2013124.","journal-title":"Artificial Intelligence"},{"key":"163064_CR36","doi-asserted-by":"crossref","unstructured":"P. Ladkin & A. Reinefeld. (1993). A symbolic approach to interval constraint problems. In J. Calmet and J. A. Campbell (eds.), Artificial Intelligence and Symbolic Mathematical Computing, volume 737 of LNCS, Springer-Verlag, pages 65\u201384.","DOI":"10.1007\/3-540-57322-4_4"},{"key":"163064_CR37","unstructured":"G. Ligozat. (1991). On generalized interval calculi. In Proc. AAAI'91."},{"key":"163064_CR38","unstructured":"G. Ligozat. (1996). A new proof of tractability for ord-horn relations. In Proc. AAAI'96."},{"key":"163064_CR39","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0004-3702(95)00109-3","volume":"87","author":"I. Meiri","year":"1996","unstructured":"I. Meiri. (1996). Combining qualitative and quantitative constraints in temporal reasoning. Artificial Intelligence 87: 343\u2013385.","journal-title":"Artificial Intelligence"},{"key":"163064_CR40","unstructured":"D. Mitchell, B. Selman, & H. Levesque. (1992). Hard and easy distributions of sat problems. In Proc. AAAI'92."},{"key":"163064_CR41","unstructured":"R. Morris, L. Khatib, & G. Ligozat. (1995). Generating scenarios from specifications of repeating events. In Proc. TIME'95."},{"key":"163064_CR42","unstructured":"I. Navarrette & R. Marin. (1997). Qualitative temporal reasoning with points and durations. In Proc. IJCAI '97, pages 1454\u20131459."},{"issue":"3","key":"163064_CR43","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF00137869","volume":"1","author":"B. Nebel","year":"1997","unstructured":"B. Nebel. (1997). Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class. CONSTRAINTS 1(3): 175\u2013190.","journal-title":"CONSTRAINTS"},{"issue":"1","key":"163064_CR44","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"B. Nebel & H. B\u00fcckert. (1995). Reasoning about temporal relations: Amaximal tractable subclass of Allen's interval algebra. Journal of the Association for Computing Machinery (ACM) 42(1): 43\u201366.","journal-title":"Journal of the Association for Computing Machinery (ACM)"},{"key":"163064_CR45","doi-asserted-by":"crossref","unstructured":"K. N\u00f6kel. (1989). Convex relations between time intervals. In J. Retti and K. Leidlmair (eds.), 5 Osterreichische Artificial-Intelligence-Tagung, pages 298\u2013302.","DOI":"10.1007\/978-3-642-74688-8_37"},{"key":"163064_CR46","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/0022-2496(70)90062-3","volume":"7","author":"P. Fishburn","year":"1970","unstructured":"P. Fishburn. (1970). Intransitive indifference with unequal indifference intervals. J. Math. Psych. 7: 144\u2013149.","journal-title":"J. Math. Psych"},{"key":"163064_CR47","unstructured":"M. Poesio & R. J. Brachman. (1991). Metric constraints for maintaining appointments: Dates and repeated activities. In Proc. AAAI'91, pages 253\u2013255."},{"key":"163064_CR48","unstructured":"E. Schwalb & R. Dechter. (1993). Coping with disjunctions in temporal constraint satisfaction problems. In Proc. AAAI'93, pages 127\u2013132."},{"key":"163064_CR49","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0004-3702(97)00009-X","volume":"93","author":"E. Schwalb","year":"1995","unstructured":"E. Schwalb & R. Dechter. (1995). Processing temporal constraint networks. Artificial Intelligence 93: 29\u201361. Also available as UCI technical report (1995).","journal-title":"Artificial Intelligence"},{"key":"163064_CR50","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R. E. Tarjan","year":"1973","unstructured":"R. E. Tarjan. (1973). Depth-first search and linear graph algorithms. SIAM J. Comput. 1: 146\u2013160.","journal-title":"SIAM J. Comput"},{"key":"163064_CR51","unstructured":"P. van Beek. (1989). Approximation algorithms for temporal reasonoing. In Proc. IJCAI'89, pages 1291\u20131296."},{"key":"163064_CR52","unstructured":"P. van Beek. (1990). Exact and Approximate Reasoning about Qualitative Temporal Relations. PhD thesis, Dept. of Computer Science, University of Alberta."},{"key":"163064_CR53","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0004-3702(92)90011-L","volume":"58","author":"P. van Beek","year":"1992","unstructured":"P. van Beek. (1992). Reasoning about qualitative temporal information. Artificial Intelligence 58: 297\u2013326.","journal-title":"Artificial Intelligence"},{"key":"163064_CR54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1613\/jair.232","volume":"4","author":"P. van Beek","year":"1996","unstructured":"P. van Beek & Dennis Manchak. (1996). The design and experimental analysis of algorithms for temporal reasoning. Journal of Artificial Intelligence Research 4: 1\u201318.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"163064_CR55","first-page":"315","volume":"3","author":"L. Vila","year":"1995","unstructured":"L. Vila & L. Godo. (1995). On fuzzy temporal constraints networks. Mathware and Soft Computing 3(1): 315\u2013334.","journal-title":"Mathware and Soft Computing"},{"key":"163064_CR56","unstructured":"M. Vilain. (1982). A system for reasoning about time. In Proc. AAAI'82, pages 197\u2013201."},{"key":"163064_CR57","doi-asserted-by":"crossref","unstructured":"M. Vilain, H. Kautz, & P. van Beek. (1989). Constraint propagation algorithms for temporal reasoning: A revised report. In Daniel S. Weld and Johan de Kleer (eds.), Readings on Qualitative Reasoning about Physical Systems. Morgan Kauffman, pages 373\u2013381.","DOI":"10.1016\/B978-1-4832-1447-4.50034-1"},{"issue":"3","key":"163064_CR58","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1111\/j.1467-8640.1993.tb00307.x","volume":"9","author":"C. P. Williams","year":"1993","unstructured":"C. P. Williams & T. Hogg. (1993). A typicality of phase transition search. Computational Intelligence 9(3): 211\u2013238.","journal-title":"Computational Intelligence"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009717525330.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009717525330\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009717525330.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:00:43Z","timestamp":1752379243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009717525330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":58,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["163064"],"URL":"https:\/\/doi.org\/10.1023\/a:1009717525330","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[1998,6]]}}}