{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:57:40Z","timestamp":1743141460560,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319135236"},{"type":"electronic","value":"9783319135243"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13524-3_7","type":"book-chapter","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T17:51:38Z","timestamp":1417542698000},"page":"75-84","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Inapproximability of Degree Anonymization"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,3]]},"reference":[{"key":"7_CR1","series-title":"Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"7_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-319-07956-1_5","volume-title":"Algorithmic Aspects in Information and Management","author":"R Bredereck","year":"2014","unstructured":"Bredereck, R., Froese, V., Hartung, S., Nichterlein, A., Niedermeier, R., Talmon, N.: The complexity of degree anonymization by vertex addition. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 44\u201355. Springer, Heidelberg (2014)"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-642-45030-3_15","volume-title":"Algorithms and Computation","author":"R Bredereck","year":"2013","unstructured":"Bredereck, R., Hartung, S., Nichterlein, A., Woeginger, G.J.: The complexity of finding a large subgraph under anonymity constraints. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 152\u2013162. Springer, Heidelberg (2013)"},{"issue":"2","key":"7_CR4","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s13278-012-0059-7","volume":"3","author":"S Chester","year":"2013","unstructured":"Chester, S., Kapron, B., Srivastava, G., Venkatesh, S.: Complexity of social network anonymization. Soc. Netw. Anal. Min. 3(2), 151\u2013166 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s13278-012-0084-6","volume":"3","author":"S Chester","year":"2013","unstructured":"Chester, S., Kapron, B.M., Ramesh, G., Srivastava, G., Thomo, A., Venkatesh, S.: Why Waldo befriended the dummy? $$k$$-anonymization of social networks with pseudo-nodes. Soc. Netw. Anal. Min. 3(3), 381\u2013399 (2013)","journal-title":"Soc. Netw. Anal. Min."},{"key":"7_CR6","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/978-1-4419-6515-8_14","volume-title":"Link Mining: Models, Algorithms, and Applications","author":"KL Clarkson","year":"2010","unstructured":"Clarkson, K.L., Liu, K., Terzi, E.: Towards identity anonymization in social networks. In: Yu, P., Han, J., Faloutsos, C. (eds.) Link Mining: Models, Algorithms, and Applications, pp. 359\u2013385. Springer, New York (2010)"},{"key":"7_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"issue":"6","key":"7_CR8","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM 48(6), 1184\u20131206 (2001)","journal-title":"J. ACM"},{"issue":"4","key":"7_CR9","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1749603.1749605","volume":"42","author":"BCM Fung","year":"2010","unstructured":"Fung, B.C.M., Wang, K., Chen, R., Yu, P.S.: Privacy-preserving data publishing: a survey of recent developments. ACM Comput. Surv. 42(4), 14:1\u201314:53 (2010)","journal-title":"ACM Comput. Surv."},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-319-07959-2_32","volume-title":"Experimental Algorithms","author":"S Hartung","year":"2014","unstructured":"Hartung, S., Hoffmann, C., Nichterlein, A.: Improved upper and lower bound heuristics for degree anonymization in social networks. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 376\u2013387. Springer, Heidelberg (2014)"},{"key":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-642-39212-2_52","volume-title":"Automata, Languages, and Programming","author":"S Hartung","year":"2013","unstructured":"Hartung, S., Nichterlein, A., Niedermeier, R., Such\u00fd, O.: A refined complexity analysis of degree anonymization in graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 594\u2013606. Springer, Heidelberg (2013)"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD \u201908), pp. 93\u2013106. ACM (2008)","DOI":"10.1145\/1376616.1376629"},{"issue":"1","key":"7_CR13","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1093\/comjnl\/bxm048","volume":"51","author":"D Marx","year":"2008","unstructured":"Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60\u201378 (2008)","journal-title":"Comput. J."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-1-4419-6045-0_14","volume-title":"Managing and Mining Graph Data","author":"X Wu","year":"2010","unstructured":"Wu, X., Ying, X., Liu, K., Chen, L.: A survey of privacy-preservation of graphs and social networks. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data, pp. 421\u2013453. Springer, Berlin (2010)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13524-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T02:25:27Z","timestamp":1676427927000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13524-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319135236","9783319135243"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13524-3_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"3 December 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}