{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T00:48:17Z","timestamp":1743122897463,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319784540"},{"type":"electronic","value":"9783319784557"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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-319-78455-7_12","type":"book-chapter","created":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T08:53:10Z","timestamp":1521535990000},"page":"154-168","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Classical Complexity and Fixed-Parameter Tractability of\u00a0Simultaneous Consecutive Ones Submatrix & Editing Problems"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4918-8150","authenticated-orcid":false,"given":"M. R.","family":"Rani","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8966-6583","authenticated-orcid":false,"given":"Mohith","family":"Jagalmohanan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9724-3484","authenticated-orcid":false,"given":"R.","family":"Subashini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,21]]},"reference":[{"issue":"21\u201323","key":"12_CR1","doi-asserted-by":"publisher","first-page":"1986","DOI":"10.1016\/j.tcs.2008.12.039","volume":"410","author":"M Oswald","year":"2009","unstructured":"Oswald, M., Reinelt, G.: The simultaneous consecutive ones problem. Theoret. Comput. Sci. 410(21\u201323), 1986\u20131992 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"12_CR2","doi-asserted-by":"publisher","first-page":"1906","DOI":"10.1137\/S0097539796303044","volume":"28","author":"H Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM J. Comput. 28(5), 1906\u20131922 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A Tucker","year":"1972","unstructured":"Tucker, A.: A structure theorem for the consecutive 1\u2019s property. J. Comb. Theory Ser. B 12(2), 153\u2013162 (1972)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"12_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(85)90042-1","volume":"55","author":"PC Fishburn","year":"1985","unstructured":"Fishburn, P.C.: Interval orders and interval graphs. Discret. Math. 55(2), 135\u2013149 (1985)","journal-title":"Discret. Math."},{"unstructured":"Oswald, M.: Weighted consecutive ones problems. Ph.D. thesis (2003)","key":"12_CR5"},{"issue":"1","key":"12_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1186\/1471-2105-7-119","volume":"7","author":"R K\u00f6nig","year":"2006","unstructured":"K\u00f6nig, R., Schramm, G., Oswald, M., Seitz, H., Sager, S., Zapatka, M., Reinelt, G., Eils, R.: Discovering functional gene expression patterns in the metabolic network of escherichia coli with wavelets transforms. BMC Bioinform. 7(1), 119 (2006)","journal-title":"BMC Bioinform."},{"issue":"3","key":"12_CR7","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"3","key":"12_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"12_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"WL Hsu","year":"2002","unstructured":"Hsu, W.L.: A simple test for the consecutive ones property. J. Algorithms 43(1), 1\u201316 (2002)","journal-title":"J. Algorithms"},{"issue":"1","key":"12_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(02)00435-8","volume":"296","author":"WL Hsu","year":"2003","unstructured":"Hsu, W.L., McConnell, R.M.: PC trees and circular-ones arrangements. Theoret. Comput. Sci. 296(1), 99\u2013116 (2003)","journal-title":"Theoret. Comput. Sci."},{"unstructured":"McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 768\u2013777. Society for Industrial and Applied Mathematics (2004)","key":"12_CR11"},{"issue":"1\u20133","key":"12_CR12","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/S0166-218X(98)00078-X","volume":"88","author":"J Meidanis","year":"1998","unstructured":"Meidanis, J., Porto, O., Telles, G.P.: On the consecutive ones property. Discret. Appl. Math. 88(1\u20133), 325\u2013354 (1998)","journal-title":"Discret. Appl. Math."},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-21875-0_25","volume-title":"Models of Computation in Context","author":"M Raffinot","year":"2011","unstructured":"Raffinot, M.: Consecutive ones property testing: cut or swap. In: L\u00f6we, B., Normann, D., Soskov, I., Soskova, A. (eds.) CiE 2011. LNCS, vol. 6735, pp. 239\u2013249. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21875-0_25"},{"key":"12_CR14","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, vol. 4. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"12_CR15","volume-title":"Recognition, Generation, and Application of Binary Matrices with the Consecutive Ones Property","author":"M Dom","year":"2009","unstructured":"Dom, M.: Recognition, Generation, and Application of Binary Matrices with the Consecutive Ones Property. Cuvillier, Gottingen (2009)"},{"issue":"4","key":"12_CR16","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1007\/s00453-012-9661-3","volume":"65","author":"P van\u2019t Hof","year":"2013","unstructured":"van\u2019t Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica 65(4), 845\u2013867 (2013)","journal-title":"Algorithmica"},{"key":"12_CR17","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2009","unstructured":"West, D.B.: Introduction to Graph Theory, vol. 2. Prentice Hall, Upper Saddle River (2009)"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-319-11812-3_27","volume-title":"Discovery Science","author":"T Uno","year":"2014","unstructured":"Uno, T., Satoh, H.: An efficient algorithm for enumerating chordless cycles and chordless paths. In: D\u017eeroski, S., Panov, P., Kocev, D., Todorovski, L. (eds.) DS 2014. LNCS (LNAI), vol. 8777, pp. 313\u2013324. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11812-3_27"},{"unstructured":"Stirling, J.: Methodus differentialis, sive tractatus de summation et interpolation serierum infinitarium, London. The Differential Method: A Treatise of the Summation and Interpolation of Infinite Series (1730). (Trans. by, J. Holliday)[1749](1730)","key":"12_CR19"},{"doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Proceedings of 10th Annual ACM Symposium on Theory of Computing, pp. 253\u2013264. ACM (1978)","key":"12_CR20","DOI":"10.1145\/800133.804355"},{"issue":"2","key":"12_CR21","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Node-deletion problems on bipartite graphs. SIAM J. Comput. 10(2), 310\u2013327 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"12_CR22","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","volume":"113","author":"A Natanzon","year":"2001","unstructured":"Natanzon, A., Shamir, R., Sharan, R.: Complexity classification of some edge modification problems. Discret. Appl. Math. 113(1), 109\u2013128 (2001)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"12_CR23","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discret. Methods 2(1), 77\u201379 (1981)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-662-48350-3_35","volume-title":"Algorithms - ESA 2015","author":"PG Drange","year":"2015","unstructured":"Drange, P.G., Dregi, M.S., Lokshtanov, D., Sullivan, B.D.: On the threshold of intractability. In: Bansal, N., Finocchi, I. (eds.) ESA 2015. LNCS, vol. 9294, pp. 411\u2013423. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_35"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78455-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T11:29:36Z","timestamp":1709810976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78455-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319784540","9783319784557"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78455-7_12","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":"21 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guangzhou","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","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":"8 May 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 May 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":"faw2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/itcs.shufe.edu.cn\/faw2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}