{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:22Z","timestamp":1725663622284},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_91","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:56:06Z","timestamp":1330257366000},"page":"418-429","source":"Crossref","is-referenced-by-count":0,"title":["Fast parallel constraint satisfaction"],"prefix":"10.1007","author":[{"given":"Lefteris M.","family":"Kirousis","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"P. Alevizos, \u201cA linear algorithm for labeling planar projections of polyhedra,\u201d Proc. IEEE\/RSJ Int. Workshop on Intelligent Robots and Systems (Osaka, Japan, 1991), 595\u2013601.","DOI":"10.1109\/IROS.1991.174541"},{"key":"35_CR2","first-page":"17","volume":"4","author":"R. Anderson","year":"1987","unstructured":"R. Anderson and E. Mayr, \u201cParallelism and greedy algorithms\u201d, Advances in Computing Research 4 (1987), 17\u201338.","journal-title":"Advances in Computing Research"},{"key":"35_CR3","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0004-3702(71)90005-1","volume":"2","author":"M. B. Clowes","year":"1971","unstructured":"M.B. Clowes, \u201cOn seeing things,\u201d Artifical Intelligence, 2 (1971), 79\u2013116.","journal-title":"Artifical Intelligence"},{"key":"35_CR4","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0020-0190(88)90069-5","volume":"27","author":"S. A. Cook","year":"1988","unstructured":"S.A. Cook and M. Luby, \u201cA simple parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula\u201d, Information Processing Letters, 27 (1988), 141\u2013145.","journal-title":"Information Processing Letters"},{"key":"35_CR5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S.A. Cook, \u201cA taxonomy of problems with fast parallel algorithms,\u201d Information and Control, 64 (1985), 2\u201322.","journal-title":"Information and Control"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, \u201cMatrix multiplication via arithmetic progressions,\u201d Proc. 28th Ann. ACM Symp. on Theory of Computing (1987), 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"35_CR7","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","volume":"55","author":"R. Dechter","year":"1992","unstructured":"R. Dechter, \u201cFrom local to global consistency,\u201d Artificial Intelligence 55 (1992), 87\u2013107.","journal-title":"Artificial Intelligence"},{"key":"35_CR8","unstructured":"N. Dendris, I. Kalafatis and L.M. Kirousis, \u201cLabelling images of the pottery world,\u201d Proc. 3rd Intl. Symp. on Algorithms and Computation, ISAAC '92 (Springer-Verlag)."},{"key":"35_CR9","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0004-3702(92)90008-L","volume":"58","author":"P. R. Cooper","year":"1992","unstructured":"P.R. Cooper and M.J. Swain, \u201cArc consistency: parallelism and domain dependence,\u201d Artificial Intelligence 58 (1992), 207\u2013235.","journal-title":"Artificial Intelligence"},{"key":"35_CR10","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E. C. Freuder","year":"1982","unstructured":"E.C. Freuder, \u201cA sufficient condition for backtrack-free search,\u201d JACM, 29 (1982), 24\u201332.","journal-title":"JACM"},{"key":"35_CR11","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"E. C. Freuder","year":"1985","unstructured":"E.C. Freuder, \u201cA sufficient condition for backtrack-bounded search,\u201d JACM, 32 (1985), 755\u2013761.","journal-title":"JACM"},{"key":"35_CR12","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","volume":"2","author":"M. Goldberg","year":"1989","unstructured":"M. Goldberg and T. Spencer, \u201cConstructing a maximal independent set in parallel,\u201d SIAM J. Discrete Mathematics, 2 (1989), 322\u2013328.","journal-title":"SIAM J. Discrete Mathematics"},{"key":"35_CR13","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P. V. Hentenryck","year":"1992","unstructured":"P.V. Hentenryck, Y. Deville, and C.-M. Teng, \u201cA generic arc-consistency algorithm and its specializations,\u201d Artificial Intelligence 57 (1992), 291\u2013321.","journal-title":"Artificial Intelligence"},{"key":"35_CR14","first-page":"295","volume":"6","author":"D. A. Huffman","year":"1971","unstructured":"D.A. Huffman, \u201cImpossible objects as nonsense sentences,\u201d Machine Intelligence, 6 (1971), 295\u2013323.","journal-title":"Machine Intelligence"},{"key":"35_CR15","doi-asserted-by":"crossref","unstructured":"R.M. Karo and V. Ramachandran, \u201cParallel algorithms for shared-memory machines,\u201d in: J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, vol. A (Elsevier, 1990), 869\u2013942.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"35_CR16","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. M. Karp","year":"1985","unstructured":"R.M. Karp and A. Wigderson, \u201cA fast parallel algorithm for the maximal independent set problem,\u201d J. Association of Computing Machinery, 32 (1985), 762\u2013773.","journal-title":"J. Association of Computing Machinery"},{"key":"35_CR17","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0004-3702(90)90009-O","volume":"45","author":"S. Kasif","year":"1990","unstructured":"S. Kasif, \u201cOn the parallel complexity of discrete relaxation in constraint satisfaction networks,\u201d Artificial Intelligence, 45 (1990), 275\u2013286.","journal-title":"Artificial Intelligence"},{"key":"35_CR18","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0022-0000(88)90043-8","volume":"37","author":"L. M. Kirousis","year":"1988","unstructured":"L.M. Kirousis and C.H. Papadimitriou, \u201cThe complexity of recognizing polyhedral scenes,\u201d Journal of Computer and System Sciences, 37 (1988), 14\u201338.","journal-title":"Journal of Computer and System Sciences"},{"key":"35_CR19","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby, \u201cA simple parallel algorithm for the maximal independent set problem,\u201d SIAM J. Computing 15 (1986), 1036\u20131053.","journal-title":"SIAM J. Computing"},{"key":"35_CR20","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","volume":"25","author":"A. K. Mackworth","year":"1985","unstructured":"A.K. Mackworth and E.C. Freuder, \u201cThe complexity of some polynomial network consistency algorithms for constraint satisfaction problems,\u201d Artificial Intelligence 25 (1985), 65\u201374.","journal-title":"Artificial Intelligence"},{"key":"35_CR21","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF00128527","volume":"1","author":"J. Malik","year":"1987","unstructured":"J. Malik, \u201cInterpreting line drawings of curved objects,\u201d International J. of Computer Vision, 1 (1987), 73\u2013103.","journal-title":"International J. of Computer Vision"},{"key":"35_CR22","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0004-3702(86)90083-4","volume":"28","author":"R. Mohr","year":"1986","unstructured":"R. Mohr and T.C. Henderson, \u201cArc and path consistency revisited,\u201d Artificial Intelligence 28 (1986), 225\u2013233.","journal-title":"Artificial Intelligence"},{"key":"35_CR23","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0004-3702(91)90059-S","volume":"48","author":"U. Montanari","year":"1991","unstructured":"U. Montanari and F. Rossi, \u201cConstraint relaxation may be perfect,\u201d Artificial Intelligence, 48 (1991), 143\u2013170.","journal-title":"Artificial Intelligence"},{"key":"35_CR24","unstructured":"P. Parodi and V. Torre, \u201cOn the complexity of labelling line drawings of polyhedral scenes\u201d, ICCV 1993, to appear."},{"key":"35_CR25","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0004-3702(92)90077-B","volume":"53","author":"M. Perlin","year":"1992","unstructured":"M. Perlin, \u201cArc consistency for factorable relations,\u201d Artificial Intelligence 53 (1992), 329\u2013342.","journal-title":"Artificial Intelligence"},{"key":"35_CR26","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF01407901","volume":"16","author":"A. Samal","year":"1987","unstructured":"A. Samal and T. Henderson, \u201cParallel consistent labeling algorithms,\u201d Int. J. Parallel Programming, 16 (1987), 341\u2013384.","journal-title":"Int. J. Parallel Programming"},{"key":"35_CR27","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/BF01407817","volume":"17","author":"M. J. Swain","year":"1988","unstructured":"M.J. Swain, \u201cComments on Samal and Henderson: \u2018Parallel consistent labeling algorithms',\u201d Int. J. Parallel Programming, 17 (1988), 523\u2013528.","journal-title":"Int. J. Parallel Programming"},{"key":"35_CR28","unstructured":"J.D. Ullman, Principles of Database Systems, 2nd ed. Computer Science Press, 1982."},{"key":"35_CR29","unstructured":"P. van Beek, \u201cOn the minimality and. decomposability of constraint networks,\u201d Proc. AAAI, 1992"},{"key":"35_CR30","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0004-3702(92)90020-X","volume":"57","author":"P. Hentenryck Van","year":"1992","unstructured":"P. Van Hentenryck, Y. Deville, and C.-M. Teng, \u201cA generic arc-consisstency algorithm and its specializations,\u201d Artificial Intelligence 57 (1992), 291\u2013321.","journal-title":"Artificial Intelligence"},{"key":"35_CR31","first-page":"19","volume-title":"The Psychology of Computer Vision","author":"D. Waltz","year":"1975","unstructured":"D. Waltz, \u201cUnderstanding line drawings of scenes with shadows,\u201d in: P.H. Winston (ed.), The Psychology of Computer Vision, (McGraw-Hill, New York, 1975), 19\u201391."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_91.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:07:34Z","timestamp":1605647254000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_91"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_91","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}