{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:46:56Z","timestamp":1725536816461},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_18","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T10:43:03Z","timestamp":1250678583000},"page":"199-210","source":"Crossref","is-referenced-by-count":0,"title":["DP-Complete Problems Derived from Extremal NP-Complete Properties"],"prefix":"10.1007","author":[{"given":"Yi","family":"Cao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph","family":"Culberson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lorna","family":"Stewart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"18_CR1","first-page":"141","volume":"7","author":"N. Abbas","year":"2005","unstructured":"Abbas, N., Culberson, J., Stewart, L.: Recognizing maximal unfrozen graphs with respect to independent sets is coNP-complete. Discrete Mathematics & Theoretical Computer Science\u00a07(1), 141\u2013154 (2005)","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"issue":"1-3","key":"18_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2005.05.003","volume":"153","author":"A. Beacham","year":"2005","unstructured":"Beacham, A., Culberson, J.: On the complexity of unfrozen problems. Discrete Applied Mathematics\u00a0153(1-3), 3\u201324 (2005)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"18_CR3","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1137\/0216022","volume":"16","author":"J.-Y. Cai","year":"1987","unstructured":"Cai, J.-Y., Meyer, G.E.: Graph minimal uncolorability is DP-complete. SIAM Journal on Computing\u00a016(2), 259\u2013277 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/3-540-18088-5_34","volume-title":"Automata, Languages and Programming","author":"J. Cai","year":"1987","unstructured":"Cai, J., Meyer, G.E.: On the complexity of graph critical uncolorability. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol.\u00a0267, pp. 394\u2013403. Springer, Heidelberg (1987)"},{"issue":"1","key":"18_CR5","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.tcs.2007.10.014","volume":"390","author":"Y. Cheng","year":"2008","unstructured":"Cheng, Y., Ko, K.-I., Wu, W.: On the complexity of non-unique probe selection. Theoretical Computer Science\u00a0390(1), 120\u2013125 (2008)","journal-title":"Theoretical Computer Science"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal, V., Szemer\u00e9di, E.: Many hard examples for resolution. Journal of the ACM\u00a035, 759\u2013768 (1988)","journal-title":"Journal of the ACM"},{"issue":"4","key":"18_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1017\/S0963548398003678","volume":"7","author":"T. Emden-Weinert","year":"1998","unstructured":"Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Combinatorics, Probability and Computing\u00a07(4), 375\u2013386 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoretical Computer Science\u00a01(3), 237\u2013267 (1976)","journal-title":"Theoretical Computer Science"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/11549345_36","volume-title":"Mathematical Foundations of Computer Science 2005","author":"J. Goldsmith","year":"2005","unstructured":"Goldsmith, J., Hagen, M., Mundhenk, M.: Complexity of DNF and isomorphism of monotone formulas. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 410\u2013421. Springer, Heidelberg (2005)"},{"key":"18_CR10","first-page":"197","volume-title":"PODS 1998: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of Database Systems","author":"P.G. Kolaitis","year":"1998","unstructured":"Kolaitis, P.G., Martin, D.L., Thakur, M.N.: On the complexity of the containment problem for conjunctive queries with built-in predicates. In: PODS 1998: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART symposium on Principles of Database Systems, pp. 197\u2013204. ACM, New York (1998)"},{"key":"18_CR11","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"18_CR12","first-page":"255","volume-title":"STOC 1982: Proceedings of the 14th annual ACM symposium on Theory of Computing","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). In: STOC 1982: Proceedings of the 14th annual ACM symposium on Theory of Computing, pp. 255\u2013260. ACM, New York (1982)"},{"issue":"1","key":"18_CR13","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(88)90042-6","volume":"37","author":"C.H. Papadimitriou","year":"1988","unstructured":"Papadimitriou, C.H., Wolfe, D.: The complexity of facets resolved. Journal of Computer and System Sciences\u00a037(1), 2\u201313 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"18_CR14","first-page":"551","volume":"12","author":"T. Riege","year":"2006","unstructured":"Riege, T., Rothe, J.: Completeness in the boolean hierarchy: Exact-four-colorability, minimal graph uncolorability, and exact domatic number problems - a survey. Journal of Universal Computer Science\u00a012(5), 551\u2013578 (2006)","journal-title":"Journal of Universal Computer Science"},{"issue":"1","key":"18_CR15","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0020-0190(03)00229-1","volume":"87","author":"J. Rothe","year":"2003","unstructured":"Rothe, J.: Exact complexity of exact-four-colorability. Information Processing Letters\u00a087(1), 7\u201312 (2003)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T07:44:30Z","timestamp":1552117470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}