{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:59:42Z","timestamp":1725544782943},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540342151"},{"type":"electronic","value":"9783540342168"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11754602_4","type":"book-chapter","created":{"date-parts":[[2006,5,20]],"date-time":"2006-05-20T07:42:06Z","timestamp":1148110926000},"page":"44-58","source":"Crossref","is-referenced-by-count":7,"title":["Partitioning Based Algorithms for Some Colouring Problems"],"prefix":"10.1007","author":[{"given":"Ola","family":"Angelsmark","sequence":"first","affiliation":[]},{"given":"Johan","family":"Thapper","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Angelsmark, O.: Constructing Algorithms for Constraint Satisfaction and Related Problems. PhD thesis, Department of Computer and Information Science, Link\u00f6pings Universitet, Sweden (2005)"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/978-3-540-45193-8_6","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"O. Angelsmark","year":"2003","unstructured":"Angelsmark, O., Jonsson, P.: Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 81\u201395. Springer, Heidelberg (2003)"},{"key":"4_CR3","unstructured":"Angelsmark, O., Jonsson, P., Thapper, J.: Two methods for constructing new CSP algorithms from old. Unpublished manuscript (2004)"},{"key":"4_CR4","first-page":"155","volume-title":"Recent Advances in Artificial Intelligience. Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS-2005)","author":"O. Angelsmark","year":"2005","unstructured":"Angelsmark, O., Thapper, J.: A microstructure based approach to constraint satisfaction optimisation problems. In: Russell, I., Markov, Z. (eds.) Recent Advances in Artificial Intelligience. Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS-2005), Clearwater Beach, Florida, USA, May 15-17, 2005, pp. 155\u2013160. AAAI Press, Menlo Park (2005)"},{"issue":"6","key":"4_CR5","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters\u00a032(6), 547\u2013556 (2004)","journal-title":"Operations Research Letters"},{"key":"4_CR6","unstructured":"Byskov, J.M.: Exact Algorithms for Graph Colouring and Exact Satisfiability. PhD thesis, Basic Research In Computer Science (BRICS), Department of Computer Science, University of Aarhus, Denmark (August 2004)"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Byskov, J.M., Eppstein, D.: An algorithm for enumerating maximal bipartite subgraphs. Unpublished manuscript (see also [6]) (2004)","DOI":"10.1002\/jgt.20041"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G.J. Chaitin","year":"1981","unstructured":"Chaitin, G.J., Auslander, M.A., Chandra, A.K., Cocke, J., Hopkins, M.E., Markstein, P.W.: Register allocation via coloring. Computer Languages\u00a06, 47\u201357 (1981)","journal-title":"Computer Languages"},{"issue":"3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"issue":"1\u20133","key":"4_CR10","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formulae. Theoretical Computer Science\u00a0332(1\u20133), 265\u2013291 (2005)","journal-title":"Theoretical Computer Science"},{"key":"4_CR11","unstructured":"Eppstein, D.: Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2001), Washington, DC, USA, January 7-9, 2001, pp. 329\u2013337. ACM\/SIAM (2001)"},{"issue":"2","key":"4_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.7155\/jgaa.00064","volume":"7","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. Journal of Graph Algorithms and Applications\u00a07(2), 131\u2013140 (2003)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/S0196-6774(02)00224-9","volume":"45","author":"T. Feder","year":"2002","unstructured":"Feder, T., Motwani, R.: Worst-case time bounds for coloring and satisfiability problems. Journal of Algorithms\u00a045(2), 192\u2013201 (2002)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/T-VT.1986.24063","volume":"35","author":"A. Gamst","year":"1986","unstructured":"Gamst, A.: Some lower bounds for a class of frequency assignment problems. IEEE Transactions on Vehicular Technology\u00a035(1), 8\u201314 (1986)","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"4_CR15","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"4_CR16","first-page":"731","volume-title":"Proceedings of the 11th (US) National Conference on Artificial Intelligence (AAAI-1993)","author":"P. J\u00e9gou","year":"1993","unstructured":"J\u00e9gou, P.: Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In: Proceedings of the 11th (US) National Conference on Artificial Intelligence (AAAI-1993), Washington DC, USA, July 1993, pp. 731\u2013736. American Association for Artificial Intelligence (AAAI), Menlo Park (1993)"},{"key":"4_CR17","unstructured":"Jonsson, P., Liberatore, P.: On the complexity of finding satisfiable subinstances in constraint satisfaction. Technical Report TR99-038, Electronic Colloquium on Computational Complexity (1999)"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1\u20132","key":"4_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science\u00a0223(1\u20132), 1\u201372 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Information Processing Letters\u00a05(3), 66\u201367 (1976)","journal-title":"Information Processing Letters"},{"key":"4_CR21","unstructured":"Robson, M.: Finding a maximum independent set in time O(2n\/4). Technical report, LaBRI, Universit\u00e9 Bordeaux I (2001)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A New Algorithm for Optimal Constraint Satisfaction and Its Implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Recent Advances in Constraints"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11754602_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T23:39:58Z","timestamp":1586907598000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11754602_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540342151","9783540342168"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11754602_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}