{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:49:54Z","timestamp":1743086994674,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_11","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"154-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Editing Graphs to Satisfy Diversity Requirements"],"prefix":"10.1007","author":[{"given":"Huda","family":"Chuangpishit","sequence":"first","affiliation":[]},{"given":"Manuel","family":"Lafond","sequence":"additional","affiliation":[]},{"given":"Lata","family":"Narayanan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"issue":"1-3","key":"11_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01585705","volume":"53","author":"Ravindra K. Ahuja","year":"1992","unstructured":"Ahuja, R.K., Goldberg, A.V., Orlin, J.B., Tarjan, R.E.: Finding minimum-cost flows by double scaling. Math. Program. 53(1\u20133), 243\u2013266 (1992)","journal-title":"Mathematical Programming"},{"key":"11_CR2","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.) ISAAC 2013. LNCS, vol. 8283, pp. 152\u2013162. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-45030-3_15"},{"issue":"1-2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0166-218X(90)90129-Z","volume":"27","author":"F. Cheah","year":"1990","unstructured":"Cheah, F., Corneil, D.G.: The complexity of regular subgraph recognition. Discrete Appl. Math. 27(1\u20132), 59\u201368 (1990)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1002\/jgt.3190030408","volume":"3","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal, V., Fleischner, H., Sheehan, J., Thomassen, C.: Three-regular subgraphs of four-regular graphs. J. Graph Theory 3(4), 371\u2013386 (1979)","journal-title":"J. Graph Theory"},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0095-8956(88)90068-8","volume":"45","author":"G Cornu\u00e9jols","year":"1988","unstructured":"Cornu\u00e9jols, G.: General factors of graphs. J. Comb. Theory Ser. B 45(2), 185\u2013198 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"11_CR6","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/s13015-017-0096-x","volume":"12","author":"R Dondi","year":"2017","unstructured":"Dondi, R., Lafond, M., El-Mabrouk, N.: Approximating the correction of weighted and unweighted orthology and paralogy relations. Algorithms Mol. Biol. 12(1), 4 (2017)","journal-title":"Algorithms Mol. Biol."},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S., Su, H.-H.: Scaling algorithms for weighted matching in general graphs. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 781\u2013800. Society for Industrial and Applied Mathematics (2017)","DOI":"10.1137\/1.9781611974782.50"},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-642-38221-5_21","volume-title":"Graph-Based Representations in Pattern Recognition","author":"A Fischer","year":"2013","unstructured":"Fischer, A., Suen, C.Y., Frinken, V., Riesen, K., Bunke, H.: A fast matching algorithm for graph-based handwriting recognition. In: Kropatsch, W.G., Artner, N.M., Haxhimusa, Y., Jiang, X. (eds.) GbRPR 2013. LNCS, vol. 7877, pp. 194\u2013203. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38221-5_21"},{"issue":"1","key":"11_CR9","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10044-008-0141-y","volume":"13","author":"X Gao","year":"2010","unstructured":"Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113\u2013129 (2010)","journal-title":"Pattern Anal. Appl."},{"key":"11_CR10","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W. H. freeman, New York (2002)"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.ic.2017.04.013","volume":"256","author":"PA Golovach","year":"2017","unstructured":"Golovach, P.A.: Editing to a connected graph of given degrees. Inf. Comput. 256, 131\u2013147 (2017)","journal-title":"Inf. Comput."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.12.007","volume":"665","author":"Petr A. Golovach","year":"2017","unstructured":"Golovach, P.A., Mertzios, G.B.: Graph editing to a given degree sequence. Theoret. Comput. Sci. 665, 1\u201312 (2017)","journal-title":"Theoretical Computer Science"},{"key":"11_CR13","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.ic.2014.12.017","volume":"243","author":"S Hartung","year":"2015","unstructured":"Hartung, S., Nichterlein, A., Niedermeier, R., Such\u1ef3, O.: A refined complexity analysis of degree anonymization in graphs. Inf. Comput. 243, 249\u2013262 (2015)","journal-title":"Inf. Comput."},{"issue":"Suppl 1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"i213","DOI":"10.1093\/bioinformatics\/bti1049","volume":"21","author":"H. Hu","year":"2005","unstructured":"Hu, H., Yan, X., Huang, Y., Han, J., Zhou, X.J.: Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics 21, i213\u2013i221 (2005)","journal-title":"Bioinformatics"},{"issue":"2","key":"11_CR15","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"John M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Lin, B.: The parameterized complexity of k-Biclique. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 605\u2013615. Society for Industrial and Applied Mathematics (2015)","DOI":"10.1137\/1.9781611973730.41"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Liu, K., Terzi, E.: Towards identity anonymization on graphs. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 93\u2013106. ACM (2008)","DOI":"10.1145\/1376616.1376629"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-642-22685-4_10","volume-title":"Computing and Combinatorics","author":"Y Liu","year":"2011","unstructured":"Liu, Y., Wang, J., Guo, J., Chen, J.: Cograph editing: complexity and parameterized algorithms. In: Fu, B., Du, D.-Z. (eds.) COCOON 2011. LNCS, vol. 6842, pp. 110\u2013121. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22685-4_10"},{"issue":"1-2","key":"11_CR19","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01889919","volume":"23","author":"L. Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz, L.: The factorization of graphs. ii. Acta Mathematica Academiae Scientiarum Hungarica, 23(1\u20132), 223\u2013246 (1972)","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.jcss.2011.02.001","volume":"78","author":"L Mathieson","year":"2012","unstructured":"Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. Sci. 78(1), 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11527923_20","volume-title":"Audio- and Video-Based Biometric Person Authentication","author":"M Neuhaus","year":"2005","unstructured":"Neuhaus, M., Bunke, H.: A graph matching based approach to fingerprint classification using directional variance. In: Kanade, T., Jain, A., Ratha, N.K. (eds.) AVBPA 2005. LNCS, vol. 3546, pp. 191\u2013200. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11527923_20"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Neuhaus, M., Bunke, H.: Bridging the Gap Between Graph Edit Distance and Kernel Machines, vol. 68. World Scientific, Singapore (2007)","DOI":"10.1142\/9789812770202"},{"issue":"7","key":"11_CR23","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1016\/j.imavis.2008.04.004","volume":"27","author":"K Riesen","year":"2009","unstructured":"Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(7), 950\u2013959 (2009)","journal-title":"Image Vis. Comput."},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-72903-7_1","volume-title":"Graph-Based Representations in Pattern Recognition","author":"K Riesen","year":"2007","unstructured":"Riesen, K., Neuhaus, M., Bunke, H.: Bipartite graph matching for computing the edit distance of graphs. In: Escolano, F., Vento, M. (eds.) GbRPR 2007. LNCS, vol. 4538, pp. 1\u201312. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72903-7_1"},{"key":"11_CR25","unstructured":"Subramanya, V.: Graph editing to a given neighbourhood degree list is fixed-parameter tractable. Master\u2019s thesis, University of Waterloo (2016)"},{"issue":"2","key":"11_CR26","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/0210021","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Edge-deletion problems. SIAM J. Comput. 10(2), 297\u2013309 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR27","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/1687627.1687631","volume":"2","author":"Zhiping Zeng","year":"2009","unstructured":"Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. Proc. VLDB Endow. 2(1), 25\u201336 (2009)","journal-title":"Proceedings of the VLDB Endowment"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 681\u2013690. ACM (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:47:41Z","timestamp":1710344861000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}