{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:32:03Z","timestamp":1725489123508},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_36","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"443-454","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Constraints on Intervals and Lengths"],"prefix":"10.1007","author":[{"given":"Andrei","family":"Krokhin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jeavons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences 7 (1974) 95\u2013132","journal-title":"Information Sciences"},{"unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)","key":"36_CR2"},{"key":"36_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1007\/3-540-45349-0_35","volume-title":"Some observations on durations, scheduling and Allen\u2019s algebra","author":"O. Angelsmark","year":"2000","unstructured":"Angelsmark, O., Jonsson, P.: Some observations on durations, scheduling and Allen\u2019s algebra. In: Proceedings of the 6th Conference on Constraint Programming (CP\u201900). Volume 1894 of Lecture Notes in Computer Science., Springer-Verlag (2000) 484\u2013488"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200 (1998) 185\u2013204","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Symposium on the Theory of Computing (STOC\u201978), New-York, ACM Press (1978) 216\u2013226","key":"36_CR5","DOI":"10.1145\/800133.804350"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Ser. B 48(1990) 92\u2013110","journal-title":"Journal of Combinatorial Theory, Ser. B"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. Allen","year":"1983","unstructured":"Allen, J.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(1983) 832\u2013843","journal-title":"Communications of the ACM"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1145\/174147.169675","volume":"40","author":"M. Golumbic","year":"1993","unstructured":"Golumbic, M., Shamir, R.: Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the ACM 40(1993) 1108\u20131133","journal-title":"Journal of the ACM"},{"unstructured":"Krokhin, A., Jeavons, P., Jonsson, P.: Reasoning about temporal relations: Tractable subalgebras of Allen\u2019s interval algebra. Technical Report RR-01-12, Oxford University Computing Laboratory (2001) Submitted for publication.","key":"36_CR9"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"Nebel, B., B\u00fcrckert, H.J.: Reasoning about temporal relations: A maximal tractable subclass of Allen\u2019s interval algebra. Journal of the ACM 42 (1995) 43\u201366","journal-title":"Journal of the ACM"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P. Goldberg","year":"1995","unstructured":"Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. Journal of Computational Biology 2 (1995) 139\u2013152","journal-title":"Journal of Computational Biology"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"M. Golumbic","year":"1994","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Advances in Applied Mathematics 15(1994) 251\u2013261","journal-title":"Advances in Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Karp, R.: Mapping the genome: some combinatorial problems arising in molecular biology. In: Proceedings of the 25th Symposium on the Theory of Computing (STOC\u201993), New-York, ACM Press (1993) 278\u2013285","key":"36_CR13","DOI":"10.1145\/167088.167170"},{"key":"36_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/3-540-56402-0_31","volume-title":"A simple test for interval graphs","author":"W.L. Hsu","year":"1993","unstructured":"Hsu, W.L.: A simple test for interval graphs. In Hsu, W.L., Lee, R., eds.: Proceedings of the 18th InternationalWorkshop on Graph-Theoretic Concepts in Computer Science. Volume 657 of Lecture Notes in Computer Science., Springer (1992) 11\u201316"},{"key":"36_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"D. Corneil","year":"1995","unstructured":"Corneil, D., Kim, H., Natarajan, S., Olariu, S., Sprague, A.: Simple linear time recognition of unit interval graphs. Information Processing Letters 55(1995) 99\u2013104","journal-title":"Information Processing Letters"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1137\/S0895480196306373","volume":"10","author":"I. Pe\u00e9r","year":"1997","unstructured":"Pe\u00e9r, I., Shamir, R.: Realizing interval graphs with size and distance constraints. SIAM Journal on Discrete Mathematics 10 (1997) 662\u2013687","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"36_CR17","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1145\/65950.65951","volume":"36","author":"C. Gabor","year":"1989","unstructured":"Gabor, C., Supowit, K., Hsu, W.: Recognizing circle graphs in polynomial time. Journal of the ACM 36 (1989) 435\u2013473","journal-title":"Journal of the ACM"},{"key":"36_CR18","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M. Golumbic","year":"1995","unstructured":"Golumbic, M., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms 19 (1995) 449\u2013473","journal-title":"Journal of Algorithms"},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0304-3975(96)00208-3","volume":"175","author":"I. Pe\u00e9r","year":"1997","unstructured":"Pe\u00e9r, I., Shamir, R.: Satisfiability problems on intervals and unit intervals. Theoretical Computer Science 175 (1997) 349\u2013372","journal-title":"Theoretical Computer Science"},{"key":"36_CR20","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF01534456","volume":"15","author":"A. Webber","year":"1995","unstructured":"Webber, A.: Proof of the interval satisfiability conjecture. Annals of Mathematics and Artificial Intelligence 15 (1995) 231\u2013238","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"36_CR21","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1613\/jair.340","volume":"7","author":"T. Drakengren","year":"1997","unstructured":"Drakengren, T., Jonsson, P.: Eight maximal tractable subclasses of Allen\u2019s algebra with metric time. Journal of Artificial Intelligence Research7 (1997) 25\u201345","journal-title":"Journal of Artificial Intelligence Research"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0004-3702(98)00093-9","volume":"106","author":"T. Drakengren","year":"1998","unstructured":"Drakengren, T., Jonsson, P.: A complete classification of tractability in Allen\u2019s algebra relative to subsets of basic relations. Artificial Intelligence 106 (1998) 205\u2013219","journal-title":"Artificial Intelligence"},{"key":"36_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0004-3702(98)00031-9","volume":"102","author":"P. Jonsson","year":"1998","unstructured":"Jonsson, P., B\u00e4ckstr\u00f6m, C.: A unifying approach to temporal constraint reasoning. Artificial Intelligence 102 (1998) 143\u2013155","journal-title":"Artificial Intelligence"},{"key":"36_CR24","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(00)00177-8","volume":"266","author":"M. Koubarakis","year":"2001","unstructured":"Koubarakis, M.: Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning. Theoretical Computer Science 266 (2001) 311\u2013339","journal-title":"Theoretical Computer Science"},{"key":"36_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science 10 (1980) 111\u2013121","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. Volume 7 of SIAM Monographs on Discrete Mathematics and Applications. (2001)","key":"36_CR26","DOI":"10.1137\/1.9780898718546"},{"key":"36_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/3-540-44693-1_36","volume-title":"The complexity of minimal satisfiability problems","author":"L. Kirousis","year":"2001","unstructured":"Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. In: Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science (STACS 2001). Volume 2010 of Lecture Notes in Computer Science., Springer (2001) 407\u2013418"},{"unstructured":"Krokhin, A., Jeavons, P., Jonsson, P.: The complexity of constraints on intervals and lengths. Technical Report TR01-077, Electronic Colloquim on Computational Complexity (2001) ( http:\/\/www.eccc.uni-trier.de\/eccc ).","key":"36_CR28"}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:00:25Z","timestamp":1556755225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}