{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:27:45Z","timestamp":1761611265566,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_71","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"835-846","source":"Crossref","is-referenced-by-count":3,"title":["Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices"],"prefix":"10.1007","author":[{"given":"Jinsong","family":"Tan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"71_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(96)00055-8","volume":"71","author":"J. Atkins","year":"1996","unstructured":"Atkins, J., Middendorf, M.: On physical mapping and the consecutive ones property for sparse matrices. Discrete Applied Mathematics\u00a071, 23\u201340 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"71_CR2","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1089\/cmb.1995.2.159","volume":"2","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F., Karp, R.M., Weisser, D.K., Zweig, G.: Physical mapping of chromosomes using unique probes. Journal of Computational Biology\u00a02, 159\u2013184 (1995)","journal-title":"Journal of Computational Biology"},{"key":"71_CR3","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.: Test for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Systems Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Systems Sci."},{"key":"71_CR4","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0020-0190(98)00186-0","volume":"69","author":"J.S. Deogun","year":"1999","unstructured":"Deogun, J.S., Gopalakrishnan, K.: Consecutive retrieval property revisited. Information Processing Letters\u00a069, 15\u201320 (1999)","journal-title":"Information Processing Letters"},{"key":"71_CR5","doi-asserted-by":"crossref","unstructured":"Flammini, M., Gambosi, G., Salomone, S.: Boolean routing. Lecture Notes in Comput. Sci, vol.\u00a0725, pp. 219\u2013233 (1993)","DOI":"10.1007\/3-540-57271-6_38"},{"key":"71_CR6","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1126\/science.1359640","volume":"258","author":"S. Foote","year":"1992","unstructured":"Foote, S., Vollrath, D., Hilton, A., Page, D.C.: The human Y chromosome: overlapping DNA clones spanning the euchromatic region. Science\u00a0258, 60\u201366 (1992)","journal-title":"Science"},{"key":"71_CR7","doi-asserted-by":"crossref","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 J. Mathematics\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Mathematics"},{"key":"71_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979)"},{"key":"71_CR9","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. Commun. ACM\u00a015, 802\u2013808 (1972)","journal-title":"Commun. ACM"},{"key":"71_CR10","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1089\/cmb.1995.2.219","volume":"2","author":"D.S. Greenberg","year":"1995","unstructured":"Greenberg, D.S., Istrail, S.: Physical mapping by STS hybridization: algorithmic strategies and the challenge of software evaluation. J. Comput. Biol.\u00a02, 219\u2013273 (1995)","journal-title":"J. Comput. Biol."},{"key":"71_CR11","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., 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, 59\u201384 (2000)","journal-title":"Theoretical Computer Science"},{"key":"71_CR12","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(01)00325-8","volume":"83","author":"M.T. Hajiaghayi","year":"2002","unstructured":"Hajiaghayi, M.T., Ganjali, Y.: A note on the consecutive ones submatrix problem. Information Processing Letters\u00a083, 163\u2013166 (2002)","journal-title":"Information Processing Letters"},{"issue":"3","key":"71_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00003","volume":"1","author":"M.M. Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Lau, H.C.: Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and 3-coloring. J. Graph Algorithm Appl.\u00a01(3), 1\u201313 (1997)","journal-title":"J. Graph Algorithm Appl."},{"issue":"5","key":"71_CR14","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1089\/106652703322539051","volume":"10","author":"W.-F. Lu","year":"2003","unstructured":"Lu, W.-F., Hsu, W.-L.: A test for the consecutive ones property on noisy data - application to physical mapping and sequence assembly. Journal of Computational Biology\u00a010(5), 709\u2013735 (2003)","journal-title":"Journal of Computational Biology"},{"key":"71_CR15","doi-asserted-by":"crossref","first-page":"565","DOI":"10.2140\/pjm.1969.28.565","volume":"28","author":"D.G. Kendall","year":"1969","unstructured":"Kendall, D.G.: Incidence matrices, interval graphs and seriation in archaeology. Pacific J. Math.\u00a028, 565\u2013570 (1969)","journal-title":"Pacific J. Math."},{"key":"71_CR16","doi-asserted-by":"crossref","unstructured":"Lewis, J.M.: On the complexity of the maximum subgraph problem. In: Proc. 10th Ann. ACM Symp. on Theory of Computing, pp. 265\u2013274 (1978)","DOI":"10.1145\/800133.804356"},{"key":"71_CR17","first-page":"237","volume":"1","author":"L. Lov\u00e1sz","year":"1966","unstructured":"Lov\u00e1sz, L.: On decomposition of graphs. Stud. Sci. Math. Hung.\u00a01, 237\u2013238 (1966)","journal-title":"Stud. Sci. Math. Hung."},{"key":"71_CR18","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, 325\u2013354 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"71_CR19","first-page":"482","volume":"22","author":"R. Mott","year":"1994","unstructured":"Mott, R., Grigoriev, A., Lehrach, H.: A algorithm to detect chimeric clones and randome noise in genomic mapping. Genetics\u00a022, 482\u2013486 (1994)","journal-title":"Genetics"},{"key":"71_CR20","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational molecular biology","author":"P.A. Pevzner","year":"2000","unstructured":"Pevzner, P.A.: Computational molecular biology. MIT Press, Cambridge (2000)"},{"key":"71_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/3-540-44968-X_38","volume-title":"Computing and Combinatorics","author":"S. Weis","year":"2000","unstructured":"Weis, S., Reischuk, R.: The complexity of physical mapping with strict chimerism. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol.\u00a01858, pp. 383\u2013395. Springer, Heidelberg (2000)"},{"key":"71_CR22","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Node- and edge-deletion NP-complete problems. In: Proc. 10th Ann. ACM Symp. on Theory of Computing, pp. 253\u2013264 (1978)","DOI":"10.1145\/800133.804355"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T19:23:09Z","timestamp":1676575389000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}