{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T09:25:34Z","timestamp":1770888334553,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,8,14]],"date-time":"2014-08-14T00:00:00Z","timestamp":1407974400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2015,3]]},"DOI":"10.1007\/s00453-014-9925-1","type":"journal-article","created":{"date-parts":[[2014,8,13]],"date-time":"2014-08-13T17:50:18Z","timestamp":1407952218000},"page":"758-773","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Obtaining Matrices with the Consecutive Ones Property by Row Deletions"],"prefix":"10.1007","volume":"71","author":[{"given":"N. S.","family":"Narayanaswamy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Subashini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,14]]},"reference":[{"issue":"1","key":"9925_CR1","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1137\/S0097539795285771","volume":"28","author":"JE Atkins","year":"1988","unstructured":"Atkins, J.E., Boman, E.G., Hendrickson, B.: A spectral algorithm for seriation and the consecutive ones problem. SIAM J. Comput. 28(1), 297\u2013310 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"9925_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(96)00055-8","volume":"71","author":"JE Atkins","year":"1996","unstructured":"Atkins, J.E., Middendorf, M.: On physical mapping and the consecutive ones property for sparse matrices. Discrete Appl Math 71(1\u20133), 23\u201340 (1996)","journal-title":"Discrete Appl Math"},{"issue":"3","key":"9925_CR3","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/s00224-012-9388-1","volume":"51","author":"G Blin","year":"2012","unstructured":"Blin, G., Rizzi, R., Vialette, S.: A faster algorithm for finding minimum tucker submatrices. Theory Comput. Syst. 51(3), 270\u2013281 (2012)","journal-title":"Theory Comput. Syst."},{"key":"9925_CR4","unstructured":"Booth, K.S.: PQ-tree algorithms. Ph.D. thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley (1975)"},{"issue":"3","key":"9925_CR5","doi-asserted-by":"crossref","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."},{"key":"9925_CR6","doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. pp. 122\u2013141. SIAM (2014)","DOI":"10.1137\/1.9781611973402.9"},{"issue":"40\u201342","key":"9925_CR7","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"9925_CR8","unstructured":"Dom, M.: Recognition, generation, and application of binary matrices with the consecutive-ones property. Ph.D. thesis, Institut fur Informatik, Friedrich-Schiller-Universitat Jena, Germany, 2008, Published by Cuvillier (2010)"},{"issue":"3\u20134","key":"9925_CR9","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/j.jcss.2009.07.001","volume":"76","author":"M Dom","year":"2010","unstructured":"Dom, M., Guo, J., Niedermeier, R.: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J. Comput. Syst. Sci. 76(3\u20134), 204\u2013221 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"9925_CR10","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Computational aspects of the helly property: a survey. J. Braz. Comput. Soc. 12(1), 7\u201333 (2006)"},{"issue":"3","key":"9925_CR11","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"9925_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, London (1979)"},{"issue":"3","key":"9925_CR13","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-Complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"9925_CR14","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1145\/361573.361578","volume":"15","author":"SP Ghosh","year":"1972","unstructured":"Ghosh, S.P.: File organization: The consecutive retrieval property. Commun. ACM 15(9), 802\u2013808 (1972)","journal-title":"Commun. ACM"},{"key":"9925_CR15","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs. Volume 57 of Annals of Discrete Mathematics. Elsevier B. V., 2nd edition (2004).","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"9925_CR16","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/aama.1994.1009","volume":"15","author":"MC Golumbic","year":"1994","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Adv. Appl. Math. 15, 251\u2013261 (1994)","journal-title":"Adv. Appl. Math."},{"issue":"1\u20132","key":"9925_CR17","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9925_CR18","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0020-0190(01)00325-8","volume":"83","author":"M Hajiaghayi","year":"2002","unstructured":"Hajiaghayi, M., Ganjali, Y.: A note on the consecutive ones submatrix problem. Inform. Process. Lett. 83(3), 163\u2013166 (2002)","journal-title":"Inform. Process. Lett."},{"key":"9925_CR19","volume-title":"Approximation Algorithms for NP-hard Problems","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997)"},{"issue":"1","key":"9925_CR20","doi-asserted-by":"crossref","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. Algorithm. 43(1), 1\u201316 (2002)","journal-title":"J. Algorithm."},{"issue":"1","key":"9925_CR21","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 296(1), 99\u2013116 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9925_CR22","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)"},{"key":"9925_CR23","first-page":"345","volume-title":"WG. Lecture Notes in Computer Science","author":"N Lindzey","year":"2013","unstructured":"Lindzey, N., McConnell, R.M.: On finding tucker submatrices and lekkerkerker-boland subgraphs. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG. Lecture Notes in Computer Science, vol. 8165, pp. 345\u2013357. Springer, Berlin (2013)"},{"key":"9925_CR24","unstructured":"McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: J. Ian Munro (ed.) Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, SODA. pp. 768\u2013777 (2004)"},{"issue":"1\u20133","key":"9925_CR25","doi-asserted-by":"crossref","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. Discrete Appl. Math. 88(1\u20133), 325\u2013354 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"18","key":"9925_CR26","doi-asserted-by":"crossref","first-page":"3721","DOI":"10.1016\/j.dam.2009.08.001","volume":"157","author":"NS Narayansaswamy","year":"2009","unstructured":"Narayansaswamy, N.S., Subashini, R.: A new characterization of matrices with the consecutive ones property. Discrete Appl. Math. 157(18), 3721\u20133727 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9925_CR27","first-page":"295","volume-title":"IPEC. Lecture Notes in Computer Science","author":"NS Narayansaswamy","year":"2013","unstructured":"Narayansaswamy, N.S., Subashini, R.: FPT algorithms for consecutive ones submatrix problems. In: Gutin, Gregory, Szeider, Stefan (eds.) IPEC. Lecture Notes in Computer Science, vol. 8246, pp. 295\u2013307. Springer, Berlin (2013)"},{"key":"9925_CR28","first-page":"239","volume-title":"CiE. Lecture Notes in Computer Science","author":"M Raffinot","year":"2011","unstructured":"Raffinot, M.: Consecutive ones property testing: cut or swap. In: L\u00f6we, B., Normann, D., Soskov, I.N., Soskova, A.A. (eds.) CiE. Lecture Notes in Computer Science, vol. 6735, pp. 239\u2013249. Springer, Berlin (2011)"},{"issue":"4","key":"9925_CR29","doi-asserted-by":"crossref","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS Robinson","year":"1951","unstructured":"Robinson, W.S.: A method for chronologically ordering archaeological deposits. Am. Antiq. 16(4), 293\u2013301 (1951)","journal-title":"Am. Antiq."},{"issue":"3","key":"9925_CR30","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9925_CR31","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00453-007-0118-z","volume":"48","author":"J Tan","year":"2007","unstructured":"Tan, J., Zhang, L.: The consecutive ones submatrix problem for sparse matrices. Algorithmica 48(3), 287\u2013299 (2007)","journal-title":"Algorithmica"},{"key":"9925_CR32","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"AC Tucker","year":"1972","unstructured":"Tucker, A.C.: A structure theorem for the consecutive ones property. Journal of Combinatorial Theory. Series B 12, 153\u2013162 (1972)","journal-title":"Journal of Combinatorial Theory. Series B"},{"issue":"17","key":"9925_CR33","doi-asserted-by":"crossref","first-page":"2312","DOI":"10.1016\/j.dam.2007.06.009","volume":"155","author":"R Wang","year":"2007","unstructured":"Wang, R., Lau, F.C.M., Zhao, Y.C.: Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices. Discrete Appl. Math. 155(17), 2312\u20132320 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9925_CR34","unstructured":"West, D.B.: Introduction to graph theory. Second edition, Prentice Hall (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9925-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9925-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9925-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T18:02:31Z","timestamp":1565719351000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9925-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,14]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,3]]}},"alternative-id":["9925"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9925-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,14]]}}}