{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:18:06Z","timestamp":1725455886251},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540637530"},{"type":"electronic","value":"9783540696421"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0017461","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:22:46Z","timestamp":1132644166000},"page":"478-490","source":"Crossref","is-referenced-by-count":3,"title":["Tractable disjunctive constraints"],"prefix":"10.1007","author":[{"given":"David","family":"Cohen","sequence":"first","affiliation":[]},{"given":"Peter","family":"Jeavons","sequence":"additional","affiliation":[]},{"given":"Manolis","family":"Koubarakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"key":"37_CR1","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0004-3702(94)90021-3","volume":"65","author":"M.C. Cooper","year":"1994","unstructured":"Cooper, M.C., Cohen, D.A., Jeavons, P.G., \u201cCharacterizing tractable constraints\u201d, Artificial Intelligence 65, (1994), pp. 347\u2013361.","journal-title":"Artificial Intelligence"},{"key":"37_CR2","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0004-3702(95)00107-7","volume":"79","author":"M.C. Cooper","year":"1995","unstructured":"Cooper, M.C., & Jeavons, P.G., \u201cTractable constraints on ordered domains\u201d, Artificial Intelligence 79, (1995), pp. 327\u2013339.","journal-title":"Artificial Intelligence"},{"key":"37_CR3","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0004-3702(92)90009-M","volume":"58","author":"R. Dechter","year":"1992","unstructured":"Dechter, R., & Pearl, J., \u201cStructure identification in relational data\u201d, Artificial Intelligence 58 (1992) pp. 237\u2013270.","journal-title":"Artificial Intelligence"},{"key":"37_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","volume":"34","author":"R. Dechter","year":"1988","unstructured":"Dechter, R. & Pearl J. \u201cNetwork-based heuristics for constraint-satisfaction problems\u201d, Artificial Intelligence 34 (1988), pp. 1\u201338.","journal-title":"Artificial Intelligence"},{"key":"37_CR5","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"E.C. Freuder","year":"1985","unstructured":"Freuder, E.C., \u201cA sufficient condition for backtrack-bounded search\u201d, Journal of the ACM 32 (1985) pp. 755\u2013761.","journal-title":"Journal of the ACM"},{"key":"37_CR6","volume-title":"Computers and intractability: a guide to NPcompleteness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., & Johnson, D.S., Computers and intractability: a guide to NPcompleteness, Freeman, San Francisco, California, (1979)."},{"key":"37_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(94)90003-5","volume":"66","author":"M. Gyssens","year":"1994","unstructured":"Gyssens, M., Jeavons, P., Cohen, D., \u201cDecomposing constraint satisfaction problems using database techniques\u201d, Artificial Intelligence 66, (1994), pp. 57\u201389.","journal-title":"Artificial Intelligence"},{"key":"37_CR8","unstructured":"Jackson, T.H., Number Theory, Routledge and Kegan Paul, (1975)."},{"key":"37_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1007\/3-540-60299-2_17","volume-title":"Proceedings 1st International Conference on Principles and Practice of Constraint Programming\u2014CP '95","author":"P. Jeavons","year":"1995","unstructured":"Jeavons, P., Cohen D., Gyssens, M., \u201cA unifying framework for tractable constraints\u201d, In Proceedings 1st International Conference on Principles and Practice of Constraint Programming\u2014CP '95 (Cassis, France, September 1995), Lecture Notes in Computer Science, 976, Springer-Verlag, Berlin\/New York, 1995, pp. 276\u2013291."},{"key":"37_CR10","unstructured":"Jonsson, P. and B\u00e4ckstr\u00f6m, C., \u201cA Linear Programming Approach to Temporal Reasoning\u201d, Proceedings of AAAI-96, (1996)."},{"key":"37_CR11","first-page":"191","volume":"20","author":"L.G. Khachian","year":"1979","unstructured":"Khachian, L.G., \u201cA polynomial time algorithm for linear programming\u201d, Soviet Math. Dokl. 20, (1979) pp. 191\u2013194.","journal-title":"Soviet Math. Dokl."},{"key":"37_CR12","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0004-3702(93)90063-H","volume":"64","author":"L. Kirousis","year":"1993","unstructured":"Kirousis, L., \u201cFast parallel constraint satisfaction\u201d, Artificial Intelligence 64, (1993), pp. 147\u2013160.","journal-title":"Artificial Intelligence"},{"key":"37_CR13","first-page":"24","volume-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR'92)","author":"M. Koubarakis","year":"1992","unstructured":"Koubarakis, M., \u201cDense Time and Temporal Constraints with \u2260\u201d, In Principles of Knowledge Representation and Reasoning: Proceedings of the Third International Conference (KR'92), (Ed. B. Nebel, C. Rich and W. Swartout), Morgan Kaufmann, San Mateo, CA, (1992), pp. 24\u201335."},{"key":"37_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/3-540-60299-2_4","volume-title":"Proceedings 1st International Conference on Principles and Practice of Constraint Programming-CP '95","author":"M. Koubarakis","year":"1995","unstructured":"Koubarakis, M., \u201cFrom Local to Global Consistency in Temporal Constraint Networks\u201d, In Proceedings 1st International Conference on Principles and Practice of Constraint Programming-CP '95 (Cassis, France, September 1995), Lecture Notes in Computer Science, 976, Springer-Verlag, Berlin\/New York, (1995), pp. 53\u201369."},{"key":"37_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/3-540-61551-2_82","volume-title":"Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming-CP '96","author":"M. Koubarakis","year":"1996","unstructured":"Koubarakis, M., \u201cTractable Disjunctions of Linear Constraints\u201d, In Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming-CP '96 (Boston, MA, August 1996), Lecture Notes in Computer Science, 1118, Springer-Verlag, Berlin\/New York, (1996), pp. 297\u2013307."},{"key":"37_CR16","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P.B. Ladkin","year":"1994","unstructured":"Ladkin, P.B., & Maddux, R.D., \u201cOn binary constraint problems\u201d, Journal of the ACM 41 (1994), pp. 435\u2013469.","journal-title":"Journal of the ACM"},{"key":"37_CR17","unstructured":"Lassez, J-L., and McAloon, K., \u201cA Canonical Form for Generalized Linear Constraints\u201d, Technical Report RC15004 (#67009), IBM Research Division, T.J. Watson Research Center, (1989)."},{"key":"37_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/3-540-50939-9_122","volume-title":"A Canonical Form for Generalized Linear Constraints","author":"J-L. Lassez","year":"1989","unstructured":"Lassez, J-L., and McAloon, K., \u201cA Canonical Form for Generalized Linear Constraints\u201d, Lecture Notes in Computer Science, 351, Springer-Verlag, Berlin\/New York, (1989), pp. 19\u201327."},{"key":"37_CR19","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"Mackworth, A.K. \u201cConsistency in networks of relations\u201d, Artificial Intelligence 8 (1977) pp. 99\u2013118.","journal-title":"Artificial Intelligence"},{"key":"37_CR20","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U., \u201cNetworks of constraints: fundamental properties and applications to picture processing\u201d, Information Sciences 7 (1974), pp. 95\u2013132.","journal-title":"Information Sciences"},{"key":"37_CR21","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0004-3702(91)90059-S","volume":"48","author":"U. Montanari","year":"1991","unstructured":"Montanari, U., & Rossi, F., \u201cConstraint relaxation may be perfect\u201d, Artificial Intelligence 48 (1991), pp. 143\u2013170.","journal-title":"Artificial Intelligence"},{"key":"37_CR22","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"Nebel, B. & Burckert, H-J., \u201cReasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra\u201d, Journal of the ACM 42, (1995), pp. 43\u201366.","journal-title":"Journal of the ACM"},{"key":"37_CR23","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J., \u201cThe complexity of satisfiability problems\u201d, Proc 10th ACM Symposium on Theory of Computing (STOC), (1978) pp. 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"37_CR24","unstructured":"Tsang, E., Foundations of Constraint Satisfaction, Academic Press, (1993)."},{"key":"37_CR25","unstructured":"van Beek, P., \u201cOn the Minimality and Decomposability of Row-Convex Constraint Networks\u201d, Proceedings of the Tenth National Conference on Artificial Intelligence, AAAI-92, MIT Press, (1992) pp. 447\u2013452."},{"key":"37_CR26","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P. Hentenryck Van","year":"1992","unstructured":"Van Hentenryck, P., Deville, Y., Teng, C-M., \u201cA generic arc-consistency algorithm and its specializations\u201d, Artificial Intelligence 57 (1992), pp. 291\u2013321.","journal-title":"Artificial Intelligence"},{"key":"37_CR27","unstructured":"Vilain, M., Kautz, H., van Beek, P., \u201cConstraint Propagation Algorithms for Temporal Reasoning: A Revised Report\u201d, In Readings in Qualitative Reasoning about Physical Systems, Ed. Weld, D.S. and de Kleer, J., Morgan Kaufmann, (1989), pp. 373\u2013381."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming-CP97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017461","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,5]],"date-time":"2019-02-05T08:49:31Z","timestamp":1549356571000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017461"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637530","9783540696421"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0017461","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}