{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T21:10:03Z","timestamp":1748466603093,"version":"3.41.0"},"publisher-location":"Cham","reference-count":13,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_10","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"121-132","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of the Minimum Independent Set Partition Problem"],"prefix":"10.1007","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhichao","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of np. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"issue":"3","key":"10_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are np-complete. Discrete Mathematics 30(3), 289\u2013293 (1980)","journal-title":"Discrete Mathematics"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. In: Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pp. 278\u2013287 (1996)","DOI":"10.1109\/CCC.1996.507690"},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Ganta, S.R., Kasiviswanathan, S.P., Smith, A.: Composition attacks and auxiliary information in data privacy. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 265\u2013273. ACM, New York (2008)","DOI":"10.1145\/1401890.1401926"},{"issue":"4","key":"10_CR7","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC 1973, pp. 38\u201349. ACM, New York (1973)","DOI":"10.1145\/800125.804034"},{"key":"10_CR9","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":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1287\/moor.26.3.583.10587","volume":"26","author":"S Onn","year":"2001","unstructured":"Onn, S., Schulman, L.J.: The vector partition problem for convex objective functions. Math. Oper. Res. 26(3), 583\u2013590 (2001)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"10_CR11","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1142\/S0218488502001648","volume":"10","author":"L Sweeney","year":"2002","unstructured":"Sweeney, L.: k-anonymity: A model for protecting privacy. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 10(5), 557\u2013570 (2002)","journal-title":"International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems"},{"key":"10_CR12","unstructured":"Wagner, D.: Find index set partition that has large projections (2013). http:\/\/cstheory.stackexchange.com\/questions\/17562\/find-index-set-partition-that-has-large-projections"},{"issue":"6","key":"10_CR13","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing 3(6), 103\u2013128 (2007)","journal-title":"Theory of Computing"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T20:33:55Z","timestamp":1748464435000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}