{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:09:29Z","timestamp":1726409369265},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_25","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T02:57:26Z","timestamp":1384829846000},"page":"295-307","source":"Crossref","is-referenced-by-count":0,"title":["FPT Algorithms for Consecutive Ones Submatrix Problems"],"prefix":"10.1007","author":[{"given":"N. S.","family":"Narayanaswamy","sequence":"first","affiliation":[]},{"given":"R.","family":"Subashini","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"25_CR1","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1137\/S0097539795285771","volume":"28","author":"J.E. Atkins","year":"1988","unstructured":"Atkins, J.E., Boman, E.G., Hendrickson, B.: A spectral algorithm for seriation and the consecutive ones problem. SIAM Journal on Computing\u00a028(1), 297\u2013310 (1988)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"25_CR2","doi-asserted-by":"publisher","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 of Computing Systems\u00a051(3), 270\u2013281 (2012)","journal-title":"Theory of Computing Systems"},{"key":"25_CR3","unstructured":"Booth, K.S.: PQ-tree algorithms. Ph.D. thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA (1975)"},{"issue":"3","key":"25_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. 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. Journal of Computer and System Sciences\u00a013(3), 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. arXiv:1211.5933v2(cs.DS) (2013)","DOI":"10.1137\/1.9781611973402.9"},{"issue":"40-42","key":"25_CR6","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0411(40-42), 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"key":"25_CR7","unstructured":"Dom, M.: Recognition, generation, and application of binary matrices with the consecutive-ones property. Ph.D. thesis, Institut fur Informatik, Friedrich-Schiller-Universitat (2008)"},{"issue":"3-4","key":"25_CR8","doi-asserted-by":"publisher","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. Journal of Computing System Sciences\u00a076(3-4), 204\u2013221 (2010)","journal-title":"Journal of Computing System Sciences"},{"issue":"1","key":"25_CR9","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF03192385","volume":"12","author":"M.C. Dourado","year":"2006","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Computational aspects of the Helly property: a survey. Journal of the Brazilian Computer Society\u00a012(1), 7\u201333 (2006)","journal-title":"Journal of the Brazilian Computer Society"},{"issue":"3","key":"25_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics\u00a015(3), 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"key":"25_CR11","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman (1979)"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363 (1974)","DOI":"10.1145\/800119.803884"},{"issue":"9","key":"25_CR13","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1145\/361573.361578","volume":"15","author":"S.P. Ghosh","year":"1972","unstructured":"Ghosh, S.P.: File organization: The consecutive retrieval property. Communications of the ACM\u00a015(9), 802\u2013808 (1972)","journal-title":"Communications of the ACM"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier B.V. (2004)","DOI":"10.1016\/S0167-5060(04)80059-1"},{"issue":"1-2","key":"25_CR15","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0234(1-2), 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"25_CR16","doi-asserted-by":"publisher","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. Information Processing Letters\u00a083(3), 163\u2013166 (2002)","journal-title":"Information Processing Letters"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"Hochbaum, D.S.: Approximation algorithms for NP-hard problems. PWS Publishing Company (1997)","DOI":"10.1145\/261342.571216"},{"key":"25_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-44679-6_23","volume-title":"Computing and Combinatorics","author":"W.L. Hsu","year":"2001","unstructured":"Hsu, W.L.: PC-trees vs. PQ-trees. In: Wang, J. (ed.) COCOON 2001. LNCS, vol.\u00a02108, pp. 207\u2013217. Springer, Heidelberg (2001)"},{"issue":"1","key":"25_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"W.L. Hsu","year":"2002","unstructured":"Hsu, W.L.: A simple test for the consecutive ones property. Journal of Algorithms\u00a043(1), 1\u201316 (2002)","journal-title":"Journal of Algorithms"},{"issue":"2","key":"25_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-Complete. Journal of Computer and System Sciences\u00a020(2), 219\u2013230 (1980)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR21","unstructured":"McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 768\u2013777 (2004)"},{"issue":"1-3","key":"25_CR22","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. Discrete Applied Mathematics\u00a088(1-3), 325\u2013354 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"3721","DOI":"10.1016\/j.dam.2009.08.001","volume":"157","author":"N.S. Narayansaswamy","year":"2009","unstructured":"Narayansaswamy, N.S., Subashini, R.: A new characterization of matrices with the consecutive ones property. Discrete Applied Mathematics\u00a0157, 3721\u20133727 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR24","doi-asserted-by":"crossref","unstructured":"Raffinot, M.: Consecutive ones property testing: cut or swap. In: Models of Computation in Context - 7th Conference on Computability in Europe, pp. 239\u2013249 (2011)","DOI":"10.1007\/978-3-642-21875-0_25"},{"issue":"4","key":"25_CR25","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"W.S. Robinson","year":"1951","unstructured":"Robinson, W.S.: A method for chronologically ordering archaeological deposits. American Antiquity\u00a016(4), 293\u2013301 (1951)","journal-title":"American Antiquity"},{"issue":"3","key":"25_CR26","doi-asserted-by":"publisher","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\u00a048(3), 287\u2013299 (2007)","journal-title":"Algorithmica"},{"key":"25_CR27","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A.C. Tucker","year":"1972","unstructured":"Tucker, A.C.: A structure theorem for the consecutive ones property. Journal of Combinatorial Theory. Series B\u00a012, 153\u2013162 (1972)","journal-title":"Journal of Combinatorial Theory. Series B"},{"issue":"17","key":"25_CR28","doi-asserted-by":"publisher","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 Applied Mathematics\u00a0155(17), 2312\u20132320 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR29","unstructured":"West, D.B.: Introduction to graph theory, 2nd edn. Prentice Hall (2001)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T06:40:27Z","timestamp":1558680027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}